자료구조 - 이진 탐색 알고리즘

▶이진 탐색 알고리즘을 적용하기 위한 조건 

: 배열에 저장된 데이터는 정렬되어 있어야 한다.

 

 

 

 

다음과 같이 정렬된 상태로 데이터가 저장되어 있다고 가정할 때

이 배열에 숫자 3이 저장되어 있는지 확인하기 위하여 이진탐색 알고리즘을 적용해보자.

▶ 이진 탐색 알고리즘의 첫 번째 시도:
1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.
2. 0과 8을 합하여 그 결과를 2로 나눈다.
3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

 

 

 

 

첫 번째 시도 결과 arr[4]에 3이 저장되지 않았음을 확인하였다.

▶ 이진 탐색 알고리즘의 두 번째 시도:
1.  arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다.
2.  대소의 비교결과는 arr[4]>3  이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.
3.  0과 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.

4.  2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

 

 

 

 

두 번째 시도 결과 arr[1]에 3이 저장되어 있지 않았음을 확인하였다.

▶ 이진 탐색 알고리즘의 세 번째 시도:
1.  arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.
2.  대소의 비교결과는 arr[1]<3  이므로 탐색의 범위를 인덱스 기준 2~3으로 제한한다.
3.  2와 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.

4.  2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

 

 

 

 

세 번째 시도 결과 탐색 대상인 3을 찾게 되어 탐색은 마무리가 된다.

 

 

 

 

 

이렇듯 이진 탐색 알고리즘은 탐색 대상과 비교하여 반씩 떨구어 내는 알고리즘이다.

 

 

코드

#include <stdio.h>

int Bsearch(int arr[], int len, int target)
{
	int first = 0;
	int last = len - 1;
	int index = 0;
	while (first <= last)
	{
		int mid = (first + last) / 2;
		if (arr[mid] == target) {    //탐색 완료
			index = mid;
			return index;
		}
		else if(arr[mid]<target)     //타겟이 더 클 때
		{
			first = mid + 1;
		}
		else                         //타겟이 더 작을 때
		{
			last = mid - 1;
		}
	}
	return -1;
}

int main() {
	int arr[] = { 1,3,5,7,9 };
	int index;

	index = Bsearch(arr, sizeof(arr)/sizeof(int), 9);
	if (index == -1)
		printf("탐색 실패\n");
	else
		printf("타겟이 저장되어 있는 인덱스 : %d\n", index);

	index = Bsearch(arr, sizeof(arr) / sizeof(int), 1);
	if (index == -1)
		printf("탐색 실패\n");
	else
		printf("타겟이 저장되어 있는 인덱스 : %d\n", index);

	return 0;

}