이진 탐색(Binary Search) 알고리즘

이진 탐색(Binary Search) 알고리즘은 배열 대상으로 적용하기 위해서는 데이터가 정렬이 되어 있어야 한다.

#include <stdio.h>
int Binary(int arr[], int len, int value)
{
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;
		if (value == arr[mid])
			return mid;
		else {
			if (value < arr[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
	}
	return -1;
}
int main()
{
	int arr[] = { 1,2,3,7,9,12,21,23,27 };
	printf("%d \n", Binary(arr, sizeof(arr) / sizeof(int), 3));

	return 0;
}

23행에서 arr 배열에 정렬된 데이터를 넣어준다.

24행에서 Binary 배열에 arr주소, 배열 길이, 찾을 값을 넣어준다.

4행에서 탐색 대상의 시작 인덱스 값을 0으로 초기화 해준다.

5행에서 탐색 새상의 마지막 인덱스 값을 넣어준다.

8행에서 조건이 last가 first보다 같거나 클때 이다.

9행에서 시작과 마지막 인덱스를 더한 후 2를 나눠준다. 그럼 배열의 중간을 찾게 된다.

13행에서 찾을 값과 arr[mid] 값이 더 크면 탐색 대상의 마지막 값을 mid - 1을 해준다.

16행에서 찾을 값이 더 크다면 탐색 대상의 시작 인덱스 값을 mid + 1을 해준다.