자료를 반으로 나누어 가면서 탐색해 값을 찾는 방법
- 자료들이 반드시 정렬되어 있어야 함
- 정렬이 되어 있다면 매우 빠르게 값을 찾을 수 있음
- 시간 복잡도 O(logN)
int BinarySearch(int start, int end, int key) {
if (start <= end) {
int mid = start + (end - start) / 2;
if (key == arr[mid]) return key;
if (key < arr[mid]) return BinarySearch(start, mid - 1, key);
if (key > arr[mid]) return BinarySearch(mid + 1, end, key);
}
return -1;
}
탐색 순서
| idx |
0 |
1 |
2 |
3 |
4 |
| value |
10 |
20 |
54 |
40 |
12 |
| idx |
0 |
1 |
2 |
3 |
4 |
| value |
10 |
12 |
20 |
40 |
54 |
| idx |
0 |
1 |
2 |
3 |
4 |
| value |
10 |
12 |
20 |
40 |
54 |
| idx |
0 |
1 |
2 |
3 |
4 |
| value |
10 |
12 |
20 |
40 |
54 |
| idx |
0 |
1 |
2 |
3 |
4 |
| value |
10 |
12 |
20 |
40 |
54 |
와 같은 순서로 탐색한다. 20을 찾기 위해선 1번, 12와 40을 찾기 위해선 2번, 10과 54를 찾기 위해선 3번의 탐색이 필요하기 때문에 O(logN)번 만에 찾을 수 있다.