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

이분 탐색이란?

 --> 정렬되어 있는 배열에서 데이터를 찾을 때 배열의 길이를 1/2만큼 줄이면서 탐색하는 방법이다.

 

아래와 같이 1에서 10까지의 숫자가 있는 배열이 있다고 해보자.

여기서 8을 이분 탐색으로 찾아보자.

 

먼저 가운데 지점을 찾는다. 이 때 left, right값을 1과 10으로 지정한 후 찾게 된다.

가운데 값과 target값(8)의 크기를 비교한다.

 

만약 가운데 값이 타겟 값보다 크다면 right = mid - 1로 바꿔준다.

만약 가운데 값이 타겟 값보다 작다면 left = mid + 1로 바꿔준다.

 

그 다음 가운데 지점을 갱신해준 뒤 가운데 값과 타겟 값을 비교한다.

 

int binary_search(int target, int n) {
	int result = 0;
	int left = 0, right = n-1;
	while(left <= right) {
		int mid = (left + right) / 2;
		if(arr[mid] > target)
			right = mid - 1;
		else if(arr[mid] < target)
			left = mid + 1;
		else {
			result = 1;
			return result;
		}
	}	
	return result;
}