[이론] 이진탐색 (Binary Search) - c++

이진탐색(Binary Search)란?

오름차순으로 정렬된 리스트에서 특정값을 찾는 알고리즘

오름차순으로 정렬된 리스트에서 중간 값(mid)을 선택하고 찾고자 하는 값(target)과 비교를 반복

때문에 정렬이 필수적

선형탐색보다 훨씬 빠르게 검색 가능(탐색 범위를 절반씩 줄여나감)

 

시간 복잡도

O(log N)

 

구현방법

1~100까지 오른차순으로 정렬된 카드 더미가 있다고 가정하자. 목표는 29를 찾는 것이다.

i번째 카드는 c[i]로 나타내고, 목표 값(target)은 val로 표현하자.

결정 문제(Decision Problem, 답이 이분적일 경우)를 "c[i] >= val ?"로 설정하고 답은 i를 증가시키며 탐색을 시작한다.

그리고 v[i] >= val이 되는 지점이 나타나면 탐색을 완료합니다.

 

목표값(target)이 있는 지점의 범위를 [lo,hi]로 설정하고 반복문의 조건은 lo +1 < hi로 범위를 절반씩 줄여가며 진행합니다.

때문의 위의 카드 더미의 경우 [1,100] -> [1,50] -> [25,50] -> [25,37] -> [25,31] -> [25,29] 

과정을 통하여 반복문을 탈출하면 됩니다. 

 

이분 탐색의 경우 구현 방법이 다양합니다.

 

먼저 반복문을 이용하여 구현하는 방법을 소개해드리겠습니다.

bool BinarySearch(int *arr, int len, int key) {
	int lo = 0;
	int hi = len - 1;
	int mid;

	while (hi - lo >= 0) {
		mid = (hi + lo) / 2;

		if (arr[mid] == key) { //탐색 종료 조건   
			return true;

		}
		else if (arr[mid] > key) {   
			hi = mid - 1;

		}
		else { 
			lo = mid + 1;

		}
	}
	return false;
}

 

재귀를 이용하여 구현

//재귀를 이용한 이진탐색
bool BinarySearch(int *arr, int lo,int hi, int key) {
	if (lo > hi) return false; 
	int mid = (lo + hi) / 2;
	if (arr[mid] == key) {
		return true;

	}
	else if (arr[mid] > key) {
		return BinarySearch(arr, lo,mid-1, key)
	}
	else {
		return BinarySearch(arr, mid + 1, hi, key);
	}
	
}

 

마지막으로 STL을 이용하여 구현하는 방법입니다.

<algorithm>헤더 파일 안에 binary_search함수가 이미 구현되어 있어 이를 이용하면 됩니다.

이진 탐색 결과 target 값이 존재한다면 1을 반환합니다. 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int n = 100;
	int arr[100];
	for (int i = 0; i < n; i++) {
		arr[i] = i;

	}
	if (binary_search(arr, arr + n, 29)) {
		cout << "값이 존재합니다. " << "\n";
	}
	return 0;
}