이진 탐색 알고리즘

순차탐색은 for문을 통해 순차적으로 검색하는 간단한 방식으로 제외한다.

 

이진탐색 알고리즘을 사용하기 위해서는 다음의 조건을 만족해야만 한다.

 

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

 

이진 탐색 알고리즘은 정렬 된 데이터가 아니면 적용이 불가능하다. 

 

길이가 8인 배열(array)에 다음과 같이 정렬된 상태로 데이터가 저장되어 있다고 가정하자.

 

여기서 숫자 1이 저장되어 있는 지 확인하기위해 이진 탐색 알고리즘은 다음과 같다.

 

1. 탐색 범위에서의 센터 값이 내가 찾고자 하는 값이 맞는 지 확인한다.

 

 

 

2. 찾은 값이 찾고자 하는 값보다 크면 탐색 범위를 왼쪽으로 줄인다.

 

 

 

3. 다시 1번을 반복한다.

 

 

4. 값을 찾을 때 까지 1~3을 반복 한다. 또는 last_idx 가 first_idx 보다 작을 때 까지 반복한다.

 

 

코드:

배열 길이 :120

찾고자 하는 값: 4

#include "stdio.h"

#define array_idx 120

int array[array_idx] =
{ 0, };

int binary_search(int *arr, int size, int search_num)
{
	int center_idx, first_idx, last_idx;
	int count;
	count = 1;
	first_idx = 0;
	last_idx = size - 1;

	while (first_idx <= last_idx)
	{
		center_idx = (first_idx + last_idx) / 2;

		if (arr[center_idx] == search_num)
			return center_idx;

		/* 중앙 idx 값이 찾고자 하는 number 보다 작으면 */
		else if (arr[center_idx] < search_num)
		{
			printf("center index value is small\r\n");
			printf("search count %d\r\n", count);
			first_idx = center_idx + 1;
		}
		/* 중앙 idx 값이 찾고자 하는 number 보다 크면 */
		else if (arr[center_idx] > search_num)
		{
			printf("center index value is large\r\n");
			printf("search count %d\r\n", count);
			last_idx = center_idx - 1;
		}

		count++;
	}
	/* No search value */
	return -1;
}

int main(void)
{
	int check_num;
	int search_number;

	for (int i = 0; i < array_idx; i++)
	{
		array[i] = i;
	}

	search_number = 4;

	check_num = binary_search(array, array_idx, search_number);

	if (check_num == -1)
	{
		printf(" no search value \r\n");
		return -1;
	}

	printf("Search number is %d \r\n", search_number);

	printf("array index is %d \r\n", check_num);

	return 0;
}

 

결과

 

 

 

Debug reports

 

else if (arr[center_idx] < search_num)
{
printf("center index value is small\r\n");
printf("search count %d\r\n", count);
first_idx = center_idx + 1;
}
/* 중앙 idx 값이 찾고자 하는 number 보다 크면 */
else if (arr[center_idx] > search_num)
{
printf("center index value is large\r\n");
printf("search count %d\r\n", count);
last_idx = center_idx - 1;
}

 

반드시 + 1 과 - 1 을 해줘야 한다. 값이 있다면 상관 없지만 값이 없는 경우 first_idx와 last_idx의 역전현상, 같아지는 경우가 없어 while (first_idx <= last_idx) 조건이 무조건 만족하게 된다.