이진 탐색

이진 탐색이란?

 

탐색의 범위를 반으로 줄여나가며 탐색하는 방식입니다. 

이미 정렬된 집합에서 빠르게 탐색할 수 있습니다. 

 

아래는 탐색 과정입니다. 

 

1. 가운데 요소를 고릅니다. (center)

2. 타깃이 가운데 요소보다 작은지, 큰지 비교합니다. 

3. 타깃이 가운데 요소보다 크다면, 가운데 요소 기준으로 오른쪽 집합으로 가서 재탐색합니다.

   (반대 쪽 집합은 탐색에서 제외되는 것입니다.)

   작다면 가운데 요소 기준으로 왼쪽 집합으로 가서 재탐색합니다. 

4. 타깃을 찾을 때 까지 위의 과정을 반복합니다. 

 

2번의 비교과정 후에, 어느 쪽 집합에서 재탐색할 지 정해지면, 탐색 범위가 반씩 줄어드므로 빠르게 탐색할 수 있습니다. 

 

 

이진 탐색의 구현 

 

매개 변수는 3개를 받습니다. 

데이터 집합(배열), 데이터 집합의 크기, 타겟값 입니다. 

 

int BinarySearch(int dataset[], int size, int target) {
	int left, right, center = 0;

	left = 0;
	right = size - 1;

	while (left <= right) { // 탐색 범위가 0 될 때 까지, 
		center = (left + right) / 2;

		if (dataset[center] == target) {
			return dataset[center];
		}
		else if(dataset[center] < target){
			left = center + 1;
		}
		else {
			right = center - 1;
		}
	}

	return NULL;

}