C++ 이진 검색(binary search)이란 무엇일까? - 대학교 컴공 2학년 자료구조 과목

이진 검색 (binary search)란 무엇인가

정렬되어 있는 배열 내에서 원하는 배열 요소를 찾아내기 위한 알고리즘으로, (오름차순일 경우) 배열을 절반으로 나누고 그 절반 값이 찾는 배열요소보다 크면 왼쪽의 토막으로 가고 찾는 배열요소의 값이 더 크면 오른쪽 토막으로 간다. 그러고 앞의 과정을 반복해 원하는 값을 찾아낸다. 
 

이진검색의 장점

선형검색, 즉 맨 앞에서부터 찾는 값이 나올 때까지 찾는 것보다 시간 복잡도가 낮아진다. 시간이 훨씬 단축된다는 것이다. 사전에서 단어를 찾을 때를 비유로 종종 들곤 하는데, 내가 '호루라기'라는 단어를 찾고 싶을 때, 맨 앞에서부터 찾으면 한세월 걸리겠지만 위와 같이 반씩 턱턱 피면서 대조하고, 다시 반절을 피고 하는 식으로 찾으면 얼마나 시간이 단축될지 체감이 될 것이다.
 

수업 때 나온 이진검색 예시코드

int BinarySearch(int* a, const int x, const int n) {
	int left = 0, right = n - 1;
	while (left <= right) {
		int middle = (left + right) / 2;
		if (x < a[middle]) right = middle - 1;
		else if (x > a[middle]) left = middle + 1;
		else return middle;
	}

	return -1;
}

코드 설명

위 코드는 main함수에서 배열 arr이 주어지고, 찾고 싶은 값 goal, 배열요소의 개수 size를 설정한 후에
BinarySearch(arr, goal, size);
와 같이 구동할 수 있다. 구동하게 되면
left를 0, right를 맨 끝값(n-1)으로 설정하고, right가 left보다 클 경우에만 구동되는 while문을 시행한다. 그 내용은, 

middle을 (left+right)/2로 정의한 후에 

goal이 arr [middle] 보다 크면 left를 middle+1로 재정의하고, (그러면 다음 반복 때 탐색할 배열이 오른쪽 토막이 된다.) goal이 arr [middle]보다 작으면 right를 middle-1로 재정의한다. (그러면 다음 반복 때 탐색할 배열이 왼쪽 토막이 된다. 만약 goal이 arr [middle]과 같으면 middle을 반환한다. (즉, 찾고 싶은 값의 index 값을 반환한다.) 그러고, while문 조건이 break날 때까지 계속 반복한다. 끝까지 반환값이 없으면 -1을 반환한다. 없다는 뜻이란다.