알고리즘 알아보기 -이분 검색-

이분 검색(이진 탐색)이란?

이분 검색(이진 탐색)은 정렬과 더불어 가장 기초적인 알고리즘 중에 하나이다.

리스트 형태의 데이터가 정렬되어 있는 상태일때 탐색 범위를 절반씩 좁혀가며 값을 찾아내는 알고리즘이다.

우리가 흔히 알고있는 업다운 게임을 생각하면 이해하기 쉽다.

동작 예시

우선 시작점과 끝점의 인덱스를 설정한다. 그리고 소숫점을 버린 중간점을 구한다.

이후 목표값과 중간점에 위치한 값을 비교한다.

중간점의 값이 더 작은 경우

중간점이 더 작은 경우 중간점 바로 다음 인덱스를 시작점으로 설정한 후 중간값을 다시 구한다. 왜냐하면 리스트는 이미 정렬되어 있으므로 중간값까지의 값은 탐색할 이유가 없기 때문이다.

중간점의 값이 더 큰 경우

중간점이 더 큰 경우 중간점 바로 이전 인덱스를 시작점으로 설정한 후 중간값을 다시 구한다. 왜냐하면 리스트는 이미 정렬되어 있으므로 중간값 이후의 값은 탐색할 이유가 없기 때문이다.

중간점의 값과 같은 경우

중간값이 목표와 같으므로 정답은 실제 코드 상 중간값인 5이다.

코드 구현

function solution(target, arr){
  arr.sort();
  let lp = 0; // 시작점
  let rp = arr.length - 1; // 끝점
  for(let i = 0; i < arr.length; i++) {
    let mid = Math.floor((lp + rp) / 2); // 중간점
    if(arr[mid] === target) return mid + 1;
    if(arr[mid] > target) rp = mid - 1;
    if(arr[mid] < target) lp = mid + 1;
  }
}