JArchive 프로그래밍 일기

이진 탐색이란?

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

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

아래는 탐색 과정입니다. 

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;

}

전제: 배열의 데이터는 정렬된 상태이다.

<순서> 

1. 배열의 중앙(mid)에 찾는 값(target)이 저장되어 있는지 확인한다.

2. 대소 결과 탐색의 대상을 반으로 줄인다.

3. 1과 2를 반복한다.

#include <stdio.h>

int BSearch(int *arr, int len, int target)
{
	int first = 0;			//탐색 시작 인덱스
	int last = len - 1;		//탐색 마지막 인덱스 
	int mid;			

	while (first <= last)    
	{
		mid = (first + last) / 2;		//mid: 중앙인덱스 
		if (target == arr[mid])
		{
			return mid;		//찾은 경우 인덱스 mid를 리턴(탐색 완료)
		}
		else  //아니라면, 탐색 대상을 반으로 줄인다 
		{
			if (target > arr[mid])
			{
				first = mid + 1;	//타겟이 더 크면 first의 위치를 옮김
			}
			else
			{
				last = mid - 1;		//타겟이 더 작으면 last의 위치를 옮김
			}
		}
	}
	return -1;	//탐색 실패한 경우 
}

int main()
{
	int arr[] = { 1, 4, 5, 7, 9, 14 };		//정렬되어 있는 배열임을 전제.
	int len = sizeof(arr) / sizeof(int);
	int index;

	index = BSearch(arr, len, 9);	//'9'를 찾아본다 
	if (index == -1)
		printf("탐색실패!\n");
	else
		printf("target의 인덱스: %d\n", index);

	return 0;
}