이진 탐색 (Binary search) 개념 및 구현
이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다.
이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다.
동작 방식
이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다.
중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다.
이진 탐색의 동작 방식은 다음과 같습니다.
- 배열의 중간 값을 가져옵니다.
- 중간 값과 검색 값을 비교합니다.
- 중간 값이 검색 값과 같다면 종료합니다. (mid = key)
- 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key)
- 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)
- 값을 찾거나 간격이 비어있을 때까지 반복합니다.
검색 예
이진 탐색을 사용하여 key = 32값을 찾는 과정을 보도록 하겠습니다.
1. 먼저 배열의 가운데를 결정합니다.
mid = low + (high - low) / 2
= 0 + (9-0)/2
= 4
2. 중앙 값과 검색 값을 비교합니다.
A [4] < key 이므로 배열의 오른쪽 구간을 검색 범위로 정합니다.
low = mid + 1
= 4 + 1
= 5
3. 중앙 값을 결정합니다.
mid = 5+ (9-5)/2
= 7
4. 중앙 값과 검색 값을 비교합니다.
A [7] > key 이므로 배열의 왼쪽 구간을 탐색 범위로 정합니다.
high = mid -1
= 7 - 1
= 6
5. 중앙 값을 결정합니다.
mid = 5 + (6-5)/2
= 5
6. 중앙 값과 검색 값을 비교합니다.
A [5] = key 이므로 탐색을 종료합니다.
시간 복잡도(Time complexity)
| Operation | Best | Average | Worst |
| Search | O(1) | Θ(log n) | O(log n) |
*n = 데이터 수
종료 조건
이진 탐색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 검색을 종료합니다.
1. 검색을 성공할 경우
- 리스트에서 검색할 값과 같은 요소를 발견한 경우
- a [mid] == key
2. 검색을 실패한 경우
- 더 이상 검색할 범위가 없을 경우
- low > high
구현
위 종료 조건을 가지고 구현을 해보겠습니다.
이진 탐색은 두 가지 구현 방법이 존재합니다.
반복문을 이용한 방법
int binarySearch (int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high-low) / 2;
if (arr[mid] == key) // 종료 조건1 검색 성공.
return mid;
else if (arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1 ; // 종료 조건2 (low > high) 검색 실패.
}
재귀 함수를 이용한 방법
int binarySearch (int arr[], int low, int high, int key) {
if (low > high) // 종료 조건2 검색 실패.
return -1;
int mid = low + (high-low)/2;
if (arr[mid] == key) // 종료 조건1 검색 성공.
return mid;
else if (arr[mid] > key)
return binarySearch(arr, low, mid-1, key);
else
return binarySearch(arr, mid+1, high, key);
}
중간 값을 구하는 방식
위 구현 방식에서 중간값은 다음 방식으로 구했습니다.
int mid = low + (high - low) / 2
단순히 다음 방식으로 중간 값을 구할 수도 있습니다.
int mid = (low + high) / 2
두번째 방식은 low + high 값이 int 값 (2^31 -1)의 범위보다 크다면 음수 값으로 오버플로우 될 것이고
이 음수 값을 2로 나누면 mid 값은 음수가 되기 때문에 문제가 될 수 있습니다.
low + high값이 범위를 넘어서는 경우가 있다면 첫번째 방식으로 중간 값을 구해야 합니다.
그렇지 않다면 두번째 방식이 연산이 간단하기 때문에 첫번째 방식보다 효율적입니다.
