이분 탐색 (Binary Search)
•
이분 탐색 (Binary Search) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법
•
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.
•
변수 3개 start, end, mid 를 사용하여 탐색한다.
동작 방식
1.
배열의 중간값을 가져온다.
2.
가져온 중간값과 검색값을 비교한다.
a.
중간값이 검색값과 같다면 종료
b.
중간값보다 검색값이 크다면 중간값을 기준으로 배열의 오른쪽 구간 탐색
c.
중간값보다 검색값이 작다면 중간값을 기준으로 배열의 왼쪽 구간 탐색
3.
값을 찾거나 간격이 비어 있을 때까지 반복
알고리즘
// 반복문
bool binary_search(vector<int>& arr, int len, int target) {
int low = 0, high = len-1;
while (low <= high) {
int mid = (low + high) / 2;
if (target == arr[mid]) return true;
if (target < arr[mid]) high = mid - 1;
else if (target > arr[mid]) low = mid + 1;
}
}
// 재귀
bool binary_search2(vector<int>& arr, int low, int high, int target) {
if (low > end) return false;
int mid = (low + high) / 2;
if (arr[mid] == target) return true;
if (arr[mid] > target) return binary_search2(arr, low, mid-1, target);
else return binary_search2(arr, mid+1, high, target);
}
C++
복사
특징
•
O(logN) 의 시간복잡도를 가진다 → 단계마다 탐색 범위를 반으로 나누는 것과 동일