[알고리즘] C++로 구현한 이진 탐색 (Binary Search)

이진 탐색

한번 반복할 때마다 탐색 범위를 반으로 줄여나가는 탐색 방법.

정렬된 데이터의 목록에만 사용이 가능하다.

 

 

 

탐색 과정

우선 어떤 방식으로 탐색이 진행되는지 알고리즘을 살펴보자. 아래의 배열에서 100을 찾아보겠다.

 

먼저 배열 중앙값인 50과 찾는 값인 100을 비교한다. 배열은 정렬되어 있고, 100은 50보다 크므로 50 이하의 값들은 탐색 대상에서 제외한다.

 

5번과 9번 배열의 중앙에 있는 7번 배열의 값인 80과 찾는 값인 100을 비교한다. 100은 80보다 크므로 80 이하의 값들은 제외한다.

 

8번과 9번 배열의 중앙에 있는 8번 배열의 값인 90과 찾는 값인 100을 비교한다. 100은 90보다 크므로 90 이하의 값들은 제외한다.

 

9번과 9번 배열의 중앙에 있는 9번 배열의 값인 100과 찾는 값인 100을 비교한다. 값이 같다는 것은 숫자를 찾았다는 것을 의미한다.

이렇게 총 4번의 반복을 통해 값을 찾을 수 있었는데, 이렇게 찾을 수 있는 경우의 수를 절반씩 줄여나가는 탐색 방법은 n에서 시작해 1에 이르기까지 반복적으로 반으로 나누는 횟수를 뜻하는 log_2(n)와 같은 형태를 보인다.

따라서 log_2(n)의 시간 복잡도를 가진다.

 

 

 

코드(c++)

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

	while (low <= high)
	{
		mid = (low + high) / 2;

		if (target < arr[mid])
			high = mid - 1;
		else if (target > arr[mid])
			low = mid + 1;
		else
			return mid;  // 반환 값은 인덱스
	}

	return -1;
}