[Algorithm] 이진탐색 - Binary Search

이진탐색은 [Hello Coding] 그림으로 개념을 이해하는 알고리즘의 가장 첫번째로 소개되는 알고리즘이다. 간단하게는 Up&Down 게임을 생각하면 쉽다. Up & Down 게임을 해보려면 여기를 통해 해보자.

 

이진탐색

이진탐색을 하기에 앞서, 단순탐색에 대해 생각해보자. 내가 0부터 100 사이의 숫자 중 하나를 선택했을 때 단순하게 내가 생각한 숫자를 맞히기 위해서는 0부터 시작해서 100까지 1씩 증가하면 된다.

const myNumber = 88;

for ( let i = 0; i < 100; i++ ) {
  if ( i === 88 ) {
    console.log("Find the number you thought! It's ${i} !");
  }
}

위의 코드처럼 0부터 1씩 증가하며 내가 생각한 숫자를 찾기 위해서는 총 88번의 연산이 필요하다.

 

이진탐색은 이런 단순한 탐색을 훨씬 빠르게 해결해준다.

그럼 대체 이진탐색이 뭘까?

이름에서 유추할 수 있듯 두개로 나누는 걸로 시작하는 게 이진탐색이다. 위의 링크를 통해 이동할 수 있는 Up & Down 게임을 해보았길 바란다. Up & Down 게임을 할 때 어떻게 해야 가장 빠르게 정답을 찾을 수 있을까?

 

1. 숫자의 가운데를 정답과 비교해본다. // 50
2. 선택한 숫자가 정답보다 작다면, 줄어든 범위의 가운데 숫자를 정답과 비교한다. // 0 ~ 49 중 이번에는 24!
3. 이런 과정을 반복하면, 최대 7번의 숫자를 선택하는 것으로 결과를 찾을 수 있다.

한 번 해보자.

const myNumber = 88;

const binarySearch = (num = 50, min = 0, max = 100) => {
  console.log("present number is ", num);
  if ( num === myNumber ) {
    return num;
  }
  if ( num < myNumber ) {
    min = num + 1;
    num = Math.floor((max+min)/2);
  } else if ( num > myNumber ) {
  	max = num-1;
    num = Math.floor((max+min)/2);
  }
  
  return binarySearch(num, min, max);
}

이처럼 이진탐색을 이용하면 최대 O(logN) 만큼의 연산만으로 원하는 결과를 얻을 수 있다.