이진 탐색 알고리즘

흔히 말하는 "업다운 게임"을 해본 사람은 이진 탐색 알고리즘을 쉽게 이해할 것이다.

1~100까지 중 어떤 수를 찾는 방법은 여러가지가 있겠지만, 업다운 게임을 할 때는 보통 절반 값을 부르고 업인지 다운인지에 따라 또 절반값을 부르는 방식으로 진행한다.

이진 탐색도 비슷하다.

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

코드 구현은 어렵지 않은 편이므로 생략하겠다.