binarySearch에 대한 이해 Javascript

binarySearch란?

배열에서 특정값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택해 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작다면 중간값을 기준으로 좌측 한칸 이동한다. X값이 중간값보다 크다면 우측으로 한칸 이동한다.

아래와 같은 배열이 있다고 가정했을 때 이진 탐색을 사용해 42를 찾을 때, 중간값은 66이다. 그럼 우선 66과 42를 비교한다. 42는 66보다 작기 때문에 좌측으로 한칸 이동해 다시 시도한다.

[16, 27, 42, 66, 87, 91, 100]

다시 시도를 하는 경우 아래에서 42를 찾는다. 이때는 중간값 27과 42를 비교하고, 42는 중간값이 27보다 크기 때문에, 우측으로 한칸 이동한다.

[16, 27, 42]

그 결과 우리는 42가 배열내에 존재한다는 것을 알 수 있고, 찾을 수 있다.

문제

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

주의 사항

• 이진탐색 알고리즘(O(logN))을 사용해야 합니다.
• 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
• target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

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

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

풀이

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let left = 0;
  let right = arr.length - 1;
  
  while(left <= right){
  	let middle = parseInt((left + right) / 2);
    if(target === arr[middle]){
    	return middle;
    }
    
    if(target < arr[middle]){
    	right = middle - 1;
    } else {
    	left = middle + 1;
    }
  }
  return -1;
};

문제를 풀 때, https://cjh5414.github.io/binary-search/ 사이트 도움을 많이 받았습니다.

문제에 대한 이해는 가능했지만, 어떤 방법으로 접근해야 좋을지 몰랐고, 다양한 블로그를 방문해본 결과 모두 같은 방법으로 문제를 해결하였습니다. 문제에 대한 접근 생각이 어려웠을 뿐 코드 작성은 쉬웠습니다.