이진검색(Binary Search)

이진검색은 정렬된 배열을 대상으로 작동함.

divide and conquer : 중간점 기준으로 찾는 값이 오른쪽, 왼쪽 어디에 있는지 찾는다. 찾는 값이 포함되지 않는 부분은 버림. 이런 방식으로 범위를 좁혀가며 원하는 값을 찾는다. (해당 배열은 정렬되어 있어야 한다.)

 

Binary Search Pseudocode:

1. 시작점(start)과 끝점(end)을 설정한다.
2. 중간점(middle)을 찾는 코드를 만든다.
3. num이 배열의 중간점과 같지 않고 시작점이 끝점보다 작을 경우에 아래의 과정을 반복한다.
4. 만약 num이 중간점 보다 작을 경우, 끝점을 중간점-1로 변경한다.
5. 만약 num이 중간점 보다 클 경우, 시작점을 중간점+1로 변경한다.
6. 중간점은 반복적으로 갱신한다.
7. 마지막으로 중간점이 찾는값과 같을 경우 찾는값 반환.
8. 그렇지 않으면 해당 값은 배열에 없으므로 -1반환.

function binarySearch(arr, num){
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);
  while (arr[middle] !== num && start <= end) {
      if(num < arr[middle]) end = middle - 1;
      else start = middle + 1;
      middle = Math.floor((start + end) / 2);
  }
  return arr[middle] === num ? middle : -1;
}