알고리즘 : 이진 탐색 (=이분 탐색, binary search)

이진 탐색은 정렬이 되어있는 N개의 데이터를 대상으로 log(N) 시간 탐색을 할 수 있는 알고리즘이다.

 

이진 탐색의 대상은 트리(특별히 이진 탐색을 위한 트리를 이진 탐색 트리, binary search tree라고 부른다.)가 될 수도 있고. 배열이 될 수 도 있다. (이경우 배열은 비교하기 위한 기준에 의해 정렬되어있어야 한다.) 심지어는 임의의 정수 영역에 대한 이진 탐색을 수행할 수도 있다.

 

만약 정렬이 되어있지 않으면 이진 탐색이 불가능하기 때문에, 이진 탐색 트리, 수 영역에 대한 이진 탐색이 아니라면 탐색의 대상을 정렬하는 행위가 선행되어야 한다. (이진 탐색 트리는 삽입 시점에서 정렬을 하면서 삽입을 한다, 수 영역은 개념적으로 정렬이 되어있다.)

 

포스팅의 예시는 배열을 대상으로 진행하며, 이진 탐색 트리의 동작은 기존에 포스팅한 자료구조 : 트리 포스팅에서 그 예시를 볼 수 있다.

---

이진 탐색의 동작과, 정렬이 되어있어야 하는 이유를 이해하기 위해 한 가지 상상을 해보자.

아주 두꺼운 책이 있다. 10000장 짜리 책이 있다고 생각하자.
그런데 이 책은 특이하게 페이지 번호가 1씩 늘어나지 않는다. (1씩 늘어났다면 1~20000 페이지까지 존재했을 것이다.)

다행히도 페이지가 감소하지는 않기 때문에 페이지 번호는 정렬되어 있다고 할 수 있다.

만약 당신이 이 책에서 5000번 페이지라고 적힌 곳을 확인하고 싶다면 어떻게 할 것 인가? (페이지 번호가 예쁘게 증가하지 않기 때문에 정 중앙이 5000번이라는 보장은 없다.)

 

사람마다 방법은 여러 가지가 나올 수 있다. 앞쪽부터 한 페이지씩 넘기며.... 까지는 아니어도 적당한 뭉텅이씩 넘기면 5000페이지를 향해 가는 사람도 있을 수 있고, 뒤에서부터 찾는 사람도 있을 수 있다.

혹은 대충 중간쯤을 열어본 뒤, 해당 페이지가 5000보다 작으면 그 페이지부터 책 끝 사이 어딘가를 다시 열어보는 식으로 찾는 사람도 있을 수 있다.

 

이중 이진 탐색의 아이디어는 "정해진 구간의 중앙을 확인 한 뒤, 중앙값이 목표보다 크다면 시작 지점부터 중앙 사이의 가운데를 다시 펼쳐보는 방식"이다. (중앙값이 작다면 당연히 중앙 ~ 끝 지점의 가운데를 다시 펴본다.)

 

만약 책의 페이지 번호가 정렬되어있지 않다면 (= 예를 들어 아예 랜덤이라면), 이 아이디어는 성립할 수가 없다.

 

그렇기 때문에 이진 탐색을 적용하기 위해서는 정렬이 필수적이다. 알고리즘 문제를 풂에 있어 정렬 비용 또한 공짜가 아니기 때문에 이진 탐색을 적용한다면 그 부분을 포함한 고민이 필요하다.

---

 

이진 탐색의 아이디어가 느낌이 왔다면 사실 구현은 간단하다.

배열을 이용한 간단한 이진 탐색의 동작 이미지를 첨부한다.