[알고리즘] 이진 검색(Binary Search) 이란?

가장 기초적인 알고리즘으로 꼽히며 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘 입니다. 이진검색의 대표적인 예로 사전을 드는데, 사전에서 단어를 검색할때 'ㄱ'부터 찾는 경우는 없을 것입니다. 우선 가장 첫번째로 쓰이는 초성을 기준으로 사전을 펼치고, 위치에 따라 앞이나 뒤쪽으로 이동하면서 검색폭을 점점 좁혀 마침내 찾는 것을 말합니다. 

검색할 항목이 있으면 가운데 지점의 값을 비교해보고 찾는 값보다 크면 뒤쪽 반을 자르고, 작으면 앞쪽 반을 자릅니다. 그리고 잘린 리스트를 대상으로 똑같은 행동을 반복합니다. 사실 이러한 행위는 재귀함수와 닮았으며, 대부분 이진검색은 비재귀로 구현되지만 본질은 재귀함수와 비슷합니다.

출처: http://glocalit.skhu.ac.kr/~mckim1/Lecture/DS/dna/index.html

다만 이진검색을 용이하게 쓰기 위해서는 데이터가 미리 정렬되어 있어야 합니다. 가운데를 잘라 크고 작은것을 판단하여 움직이기 때문에 만약 정렬되어 있지 않다면 쓰기 곤란한 단점을 가집니다. 그래서 연결리스트 같은 것은 이진검색을 쓰기 힘듭니다. 연결리스트는 이전이나 다음의 노드의 위치를 함꼐 저장하기에 정렬이 필요한 이진검색에서는 사용하기 힘듭니다. 

이진검색을 사용하는 실행횟수를 획기적으로 줄여주기 때문입니다. 만약 100개의 길이가 있는 배열이 있고 73번째에 데이터가 있다고 한다면, 순서대로 데이터를 점검했을 때 0~73번까지 하나씩 검토를 하면서 넘어가기 때문에 총 73번이 실행되어야 합니다. 이를 시간복잡도로 O(n)으로 표기합니다. 

반면에 이진검색의 경우는 첫번째 0과 100을 더해 2를 나누어 나오는 숫자인 50으로 접근합니다(1회실행). 73은 50보다 크기 때문에 이번에는 (50 + 100) / 2 를 실행하여 나온 75로 접근합니다(2회실행). 73은 75보다 작으므로 이면엔 (50 + 75) / 2 를 실행하여 62를 접근합니다(3회실행). 이런식으로 차이를 점점 좁혀서 검색하고자 하는 값을 찾을 수 있습니다. 

그래서 식으로 정리하면 O(log n)이 됩니다.

이진검색의 또다른 장점은 데이터가 많아질수록 다른 알고리즘에 비해 속도가 매우 빠르다는 점입니다. 1번의 함수가 실행되는데 1초가 걸린다고 하면 순차검색의 경우 데이터의 크기 x 1초 의 시간이 소요됩니다. 그에반해 이진검색은 아래의 표처럼 처리시간량이 크게 늘어나지 않는 장점을 지닙니다.