이진탐색 (Binary Search) 알고리즘.
N개의 데이터를 가진 배열 list[]가 있고, 우리가 찾고자 하는 값이 key라고 하자( list[0], list[1], ..., list[N-1] ).
이진 탐색은 배열의 중간요소(list[N/2])와 찾고자하는 값(key)을 비교한다. 찾고자하는 값이 중간요소 보다 작다면 배열의 중간요소 보다 큰 요소들(list[N/2] ... list[N-1])에는 찾고자 하는 데이터가 없는 것이다. 즉, 데이터의 절반은 검사 할 필요가 없어진다.
나머지 요소들에 대해 똑같이 반복한다.
탐색방법
입력 : 리스트,시작인덱스,마지막인덱스,검색값
출력 : 해당 키의 인덱스 ( 찾는 값이 있으면 ) 또는 아니오 ( 찾는 것이 없으면)
1. 각 값의 의미
head : 찾고자 하는 리스트 의 처음
tail : 찾고자 하는 리스트의 끝
mid : head 와 end의 중간 값
2. 리스트의 중간에 있는 원소의 키(list[mid]) 와 탐색하려는 값 key를 비교
한다.
이진 탐색 알고리즘
+--------------------------------------------------------------------+
| 1. 중간요소를 구한다. mid = (head + tail ) / 2 |
| 2. 중간요소보다 key값이 크면, mid를 head 로 한다. |
| 3. 중간요소보다 key값이 작으면, mid를 tail로 한다. |
| 4. head <= tail인 동안 1에서 3을 반복 |
| 5. 중간요소와 key가 같으면 찾았음, 그렇지 않으면 찾지 못함. |
+--------------------------------------------------------------------+
key = 61
1) 중간요소를 구한다.
↓head ↓tail
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0] [1] [2] [3] [4] [5] [6] [7] [8]
↑
mid = (head + tail) / 2
2) 중간요소보다 key값이 크면, mid를 head로 하고, 중간요소를 구한다.
↓head ↓tail
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0] [1] [2] [3] [4] [5] [6] [7] [8]
↑
mid = (head + tail) / 2
3) 중간요소보다 key값이 작으면, mid를 tail로 하고, 중간요소를 구한다.
↓head ↓tail
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0] [1] [2] [3] [4] [5] [6] [7] [8]
↑
mid = (head + tail) / 2
4) 중간요소 = key. 찾았음
↓head ↓tail
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0] [1] [2] [3] [4] [5] [6] [7] [8]
↑
list[mid] = key
이 이진 탐색 알고리즘은 간단하면서도 무척 빠르다. 이진 탐색의 큰 단점은 소트된 데이터에만 적용이 가능하다는 점이다. 따라서, 이진탐색을 하기전에 반드시 소트를 해야만 한다.
수시로 데이터가 입력되고 조회되어야 하는 온라인(on-line)시스템에서 이진 탐색을 사용한다는 것은 힘든 일이다. 데이터가 입력 될때 마다 소트를 해야하기때문이다. 그러나, 수집된 데이터를 하루 혹은 일주일 단위로 한꺼번에 처리하는 일괄처리(batch)작업에서는 아주 좋은 효과를 볼수있다.
