[ 알고리즘 ] 이진 탐색 ( Binary Search )

이진 탐색 ( Binary Search )

업 앤 다운이라는 게임이 있다. 이 게임의 룰은 사회자가 1~100 사이의 숫자를 정한 뒤 그 숫자를 돌아가면서 맞추는 게임으로 부른 숫자가 사회자가 부른 숫자보다 낮으면 Up, 부른 숫자가 사회자가 부르는 숫자보다 높은 숫자면 Down 이라고 해서 그 숫자를 맞추는 게임이다.

이 게임에서 가장 빠른 방법은 당연히 운빨로 한번에 맞추는거겠지만, 평균에 수렴하게 되면 가장 빠르게 답을 찾을 수 있는 방법은 절반값을 계속 불러서 답을 찾아가는 방식이다.

이런식으로 값을 찾아가는 방식이 바로 이진 탐색 방식이다. 

이 방식을 사용하면 100에서 값을 찾는데 걸리는 최악의 경우 logn ( 이진 로그) 으로 6.64 정도, 아무리 최악의 상황에도 7번 안에 답을 찾을 수 있는 방법인 것이다.

하지만 이진 탐색에는 치명적 약점이 있는데, 미리 정렬되지 않은 데이터셋에는 사용할 수 없다는 단점이 있다.