이진탐색 알고리즘 (binary search)

이진탐색 알고리즘이란?

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 찾는 값(target)과 중간값(mid)을 비교하여, 그 결과에 따라 탐색 범위를 계속해서 재설정하는 방식이다.

문제

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

예시

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

수도 코드

(index 기준)시작점(start): 0, 끝점(end): arr.length -1, 중간점(mid): Math.floor((시작점 + 끝점) / 2)
[target과 mid를 비교]
1. (target = mid)라면 / 탐색 종료
2. (target < mid)라면 / target은 mid의 좌측에 있음 => 배열의 끝점을 mid - 1로 옮겨서 재탐색
3. (target > mid) / target은 mid의 우측에 있음. => 배열의 시작점을 mid + 1로 옮겨서 재탐색

4. (반복 조건) 시작점 <= 끝점일 동안만 (배열 수정을 반복하다가 시작점 > 끝점이 되면 (즉, target이 없으면) 반복 종료)

---

5. target이 없으면 => return -1

풀이

const binarySearch = function (arr, target) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    //mid를 구할 때 값을 올림하든, 버림하든 상관없음. 정수로만 나오면 됨

    if(target === arr[mid]) {
      return mid;
    };

    if (target < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  } 

  return -1;
};