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

이분 탐색, 이진 검색, 혹은 이진 탐색 알고리즘은 정렬이 끝난 배열(리스트)에서 특정 값을 찾는 알고리즘이다.

 

정렬이 끝난 배열을 계속해서 반으로 나누어 탐색 범위를 좁히기 때문에 시간 복잡도는 $O(\log{N})$으로 빠르다.

 

말로만 설명하면 잘 와닿지 않을 수도 있으니 가장 간단한 상황 중 하나를 그림으로 그려보도록 하겠다.

 

위와 같이 정렬이 끝난 배열에서 7의 위치를 찾는 과정을 이분탐색으로 따라가 보자.

 

먼저 중간값(5)을 기준으로 7이 작은지 큰지 확인한 후 반쪽을 버린다.

 

이어서 다음 중간값인 8과 비교해 역시 나머지 절반을 버린다.

 

마지막 중간값이 7과 같으므로 탐색을 종료한다.

 

이처럼 매우 단순한 알고리즘이기 때문에 전공생들은 보통 1학년 초반에 배운다고 한다.

 

추가로 구현은 일반적으로 반복문 혹은 재귀문으로 구현된다고 한다.

 

이진 탐색 문제, 풀러 가보자!