이진 탐색

이진 탐색은 순차 탐색에 비해 평균적으로 빠르지만 탐색에 대상이 되는 배열이 정렬된 상태임이 보장되어야 한다.

또 정렬된 배열이 오름차순인지 내림차순인지 따라 내부 구현이 살짝 달라지게 된다.

여기서는 오름차순 배열을 대상으로 하겠다.

  

int bin_search(int * arr, int len, int target)
{
	int l = 0, r = len - 1;
	int mid;

	while (l <= r)
	{
		mid = (l + r) / 2;
		if (arr[mid] == target)
			return mid;
		else if (arr[mid] < target)
			l = mid + 1;
		else
			r = mid - 1;
	}

	return -1;
}

"l" 은 left 인덱스이고, "r" 은 right 인덱스이다.

그래서 두 인덱스의 중간값을 구하고 그 인덱스가 위치한 배열의 값과 탐색하고자 하는 값을 비교하는데,

발견하면 이 인덱스 값을 바로 반환하면 되는 것이고,

그렇지 않다면 다음에 사용 할 인덱스 값을 조정하게 된다.

 

먼저 찾고자하는 값보다 작은 경우이다.

mid      <      target      <       right

배열은 정렬되어 있기 때문에 위와 같은 경우가 된다.

mid는 이미 탐색하였기 때문에 mid + 1 을 새로운 left값으로 잡는 것이다.

 

큰 경우는 아래와 같다.

left      <     target       <       mid

반대로 mid - 1을  새로운 right로 잡게된다.

 

그래서 이러한 작업을 left 가 right를 넘어서지 않을 때 까지 반복하는 것이고,

반복문을 빠져나오게 되면 left가 right를 넘어서는 상황이 발생하게 되기 때문에

타겟이 배열내에 없음을 반환하는 것이다.