이진탐색이란

이진탐색(Binary Search)

정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.
이진 탐색 알고리즘(二進探索algorithm, Binary Search Algorithm)은 컴퓨터과학, 수학 등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

알고리즘 구현 방법

사진과 같이 특정 수를 찾고 싶을 때
1. 전체 범위의 min, max를 구한다.
2. 전체 범위의 mid를 구한다.
3. 우리가 찾고싶은 수가 mid 이전인지 이후인지 구한다.
4. 이전이면 mid가 새로운 max가 되고, 이후이면 mid가 새로운 min이 된다.
5. 1~3번 연산을 다시한번 실행한다.

위와 같은 방법으로 점점 범위를 좁혀나가 우리가 찾고자 하는 수가 나올 때까지 반복하면 된다.

알고리즘 특징

이진 탐색은 처음부터 끝까지 순서대로 찾는 순차 탐색에 비해 굉장히 빠르지만, 사전을 든 예시에서 볼 수 있듯이 미리 정렬이 되어 있어야 되는 점, 경우에 따라서는 쓰기 곤란한 경우도 있다는 점이 단점이다. 이를테면 연결 리스트 같은 것에 이진 탐색을 쓰기 곤란하다. 연결 리스트는 자기테이프같은 구조라 무작위 위치로 점프하질 못하고 앞뒤로 움직이기만 가능하기 때문이다. 물론 약간의 트릭을 쓰면 연결 리스트에서 이진 탐색이 가능하다.

${\mathcal O}$(${\rm lb}$ $n$) 의 위력이 감이 잘 안온다면, 4,294,967,296개(약 43억개)의 원소가 있는 리스트에서 원하는 특정 값을 찾아낼 때 최악의 탐색 깊이(찾는 값이 없는 경우)는 딱 32회이다. 그러나 순차 탐색의 최악의 경우는 4,294,967,296회이다. 저게 0부터 순서대로 숫자가 들어있는 리스트라고 할 때 순차 탐색이 이진 탐색보다 빠른 지점은 32까지. 33부터 그 나머지 구간에서는 이진 탐색이 순차 탐색보다 빠르다. 33회의 비교시에는 약 86억개의 자료를 탐색할 수 있다. 우주에 존재하는 모든 원자 개수만큼의 원소를 가지는 리스트를 주어줘도 약 120회 정도만 비교하면 원하는 값을 찾을 수 있다.