[알고리즘] 이분탐색 (Binary Search)

이진탐색이란?

이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

이진탐색 구현

구현방법에는 두가지가 있다.

1. 반복문을 이용한 방법

int BinarySearch(int arr[], int target, int size) {
	int first = 0;
	int last = size - 1;
	int mid;

	while (first <= mid) {
		mid = (first + mid) / 2;

		if (arr[mid] == target)
			return mid;
		else if (arr[mid] < target)
			last = mid - 1;
		else
			first = mid + 1;
	}
	return -1; //못찾았을 경우
}

2. 재귀함수를 이용한 방법

int BSrecursion(int arr[], int target, int first, int last) {
	if (first > last) return -1;

	int mid = (first + last) / 2;
	if (arr[mid] == target)
		return mid;
	else if (arr[mid] > target)
		return BSrecursion(arr, target, first, mid - 1);
	else
		return BSrecursion(arr, target, mid - 1, last);
}