이진탐색 Binary Search

이진 탐색 알고리즘을 사용하기 위해서는 배열에 저장된 데이터가 정렬되어있어야 한다. 다시 말해서 정렬되지 않은 배열에는 이진 탐색 알고리즘을 사용할 수 없다. 이진 탐색은 탐색의 범위를 반복해서 절반씩 줄이는 알고리즘이다.

 

배열 { 1,3,5,6,7,9,11,13,15,19 }에서 3을 찾는 과정은 다음과 같다.

 

첫 번째 시도

1	3	5	6	7	9	11	13	15	19
arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]	arr[9]	arr[10]

1. 배열 인덱스의 시작과 끝을( 0과 10 ) 더해서 2로 나눈다.

2. 0과 10을 더해서 나눈 결과 5를 인덱스 값으로 해서 저장된 값이 3인지 확인한다.

 

 

두 번째 시도

1. arr[5]에 저장된 값이 3이 아님을 알았으니 arr[5]의 값과 3의 대소를 비교한다. 

2. 3은 arr[5]의 값인 7 보다 작으므로 탐색의 범위를 0 ~ 4로 제한한다.

3. 0과 4를 더해서 그 결과를 2로 나눈다.

4. 0과 4를 더해서 나눈 결과 2를 인덱스 값으로 해서 저장된 값이 3인지 확인한다.

5. arr[2]의 값이 3이 맞으므로 탐색을 종료한다.

 

 

Code

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
	int first = 0;			//탐색대상의 첫 인덱스
	int last = len - 1;		//탐색대상의 끝 인덱스
	int mid;

	while (first <= last)	//first와 last가 같은 경우 까지 검사하여야 마지막하나까지 검사할수있다.
	{
		mid = (first + last) / 2;		//탐색 대상의 가운데를 찾는다.
		if (target == ar[mid]) return mid;	//가운데 저장된것이 타겟값이라면 탐색을 종료한다.
		else
		{
			if (target < ar[mid]) last = mid - 1;	//찾고자 하는 수가 중앙의 수보다 작으면
			else first = mid + 1;			//찾고자 하는 수가 중앙의 수보다 크면
		}
	}
	return -1;
}

int main(void)
{
	int arr[] = { 1,3,5,6,7,9,11,13,15,19 };
	int index;

	index = BSearch(arr, sizeof(arr) / sizeof(int), 3);	//arr에 3을 탐색
	if (index == -1) printf("해당값 없음\n");
	else printf("타겟의 위치 : %d\n", index);
	
	return 0;
}

종료 조건

이진 탐색 알고리즘의 종료 조건은 찾고자 하는 값을 찾았거나, first가 last보다 큰 경우이다. 후자의 경우에는 탐색 실패를 뜻한다.