JavaScript로 이진탐색(Binary Search) 알고리즘 구현하기

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

이진탐색(O(logN))은 단순한 배열 순회(O(N))보다 시간복잡도에서 크게 이점을 같는다

수도코드를 작성해보면

입출력 예시로 아래가 있다.

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

1. 가운데 위치한 임의의 값 3을 선택한다.
2. 선택한 값 3과 찾고자 하는 값 2를 비교한다
3. 2<3이므로 2는 3의 좌측에 존제한다는 것을 알 수 있다.
4. [0, 1, 2]를 대상으로 다시 탐색을 진행한다.
5. 마찬가지로 가운데 임의의 값 1을 선택한다.
6. 1<2이므로 [2]를 남겨두고 또 다시 탐색을 진행한다.
7. 종료조건: 중간값이 찾는 값과 같을 경우까지 반복...
8. 반복의 범위: 남겨진 배열들이 계속 짧아지면서 start 시점이 end 시점보다 커질때까지
9. 반복문을 나왔을 때 리턴값을 찾지 못하면 찾는값이 배열에 없다는 것과 같으므로 -1리턴

코드를 종합해보면

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let start = 0;
  let end = arr.length-1
  let mid
  
  while(start<=end){ //점점 좁혀지다가 start와 end의 순서가 어긋나게 되면 반복을 종료한다
  
  mid = parseInt((start+end)/2)
  
  if(target === arr[mid]){
    return mid;
  } else{
    if(target<arr[mid]){
      end = mid-1
    }
    else{
      start = mid+1
    }
  }
  }
  return -1

};

• 재귀함수를 사용해서도 한 번 풀어봐야겠다.