[C] 이진 탐색 알고리즘 (Binary Search) (배열)

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

 

<순서> 

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;
}