이진 탐색

이진 탐색(Binary-Search) 이란 정렬된 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 원하는 값을 찾는 알고리즘이다.

반드시 리스트(배열)을 정렬해서 사용해야하며 재귀, 반복문, STL을 이용하여 이진 탐색을 실행할 수 있다. 이진 탐색의 시간 복잡도는 O(log N) 이다.

다음의 배열에서 원소 7 을 이진 탐색하면 다음과 같은 과정으로 이루어진다.

1. 검사 범위의 시작점 Left 과 끝점 Right 를 설정한다.

int Left = 0, Right = Nums.size() - 1;

검사 범위 설정

1. 검사 범위에서 중간 위치 Mid 를 구해 찾고자 하는 값 7 과 비교한다.

	int Target = 7;
	int Mid = (Left + Right) / 2;

중간 위치 Mid를 구한다.

1. 만약 찾고자 하는 값보다 작다면 Mid < Target 검사 범위를 큰 쪽으로 잡아야 한다. 그러므로 Left = Mid + 1 을 한다.

   만약 찾고자 하는 값보다 크다면 Mid > Target 검사 범위를 작은 쪽으로 잡아햐 한다. 그러므로 Right = Mid - 1 을 한다.

	if (Nums[Mid] < Target)
		Left = Mid + 1;
	
	if (Nums[Mid] > Target)
		Right = Mid - 1;

Target > Nums[Mid] 이므로 Right = Mid - 1

1. 1 ~ 3번 과정을 반복하다가 원하는 값이 나오면 결과를 반환하고, 검사할 곳이 없으면 Left > Right 로 돌아간다.

	while (Left <= Right)
	{
		int Mid = (Left + Right) / 2;
		if (Nums[Mid] == Target)
			break;

		if (Nums[Mid] < Target)
			Left = Mid + 1;

		if (Nums[Mid] > Target)
			Right = Mid - 1;
	}

예시

위의 과정을 코드로 작성하면 다음과 같다.

반복문을 이용하는 경우

#include <iostream>
#include <vector>

int main() 
{
	std::vector<int> Nums = { 2, 4, 7, 8, 9, 11, 14, 17, 20, 23 };
	int Left = 0, Right = Nums.size() - 1;
	
	int Target = 7;
	while (Left <= Right)
	{
		int Mid = (Left + Right) / 2;
		if (Target == Nums[Mid])
		{
			std::cout << "Target Index : " << Mid;
			break;
		}

		if (Nums[Mid] < Target)
			Left = Mid + 1;

		if (Nums[Mid] > Target)
			Right = Mid - 1;
	}
	
	return 0;
}

Target Index : 2

재귀를 이용하는 경우

#include <iostream>
#include <vector>

void BinarySearch(std::vector<int>& Arr, int Left, int Right, int Target)
{
	if (Left > Right)
		return;

	int Mid = (Left + Right) / 2;
	if (Arr[Mid] == Target)
	{
		std::cout << "Target Index : " << Mid;
		return;
	}

	if (Arr[Mid] < Target)
		BinarySearch(Arr, Mid + 1, Right, Target);

	if (Arr[Mid] > Target)
		BinarySearch(Arr, Left, Mid - 1, Target);
}

int main() 
{
	std::vector<int> Nums = { 2, 4, 7, 8, 9, 11, 14, 17, 20, 23 };
	BinarySearch(Nums, 0, Nums.size() - 1, 11);
	
	return 0;
}

Target Index : 5

STL을 이용하는 경우

STL에서 지원하는 std::binary_search 를 이용할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
	std::vector<int> Nums = { 2, 4, 7, 8, 9, 11, 14, 17, 20, 23 };

	int Target = 17;
	bool isFind = std::binary_search(Nums.begin(), Nums.end(), Target);
	if (isFind)
		std::cout << Target << " is Exist.\\n";
	else
		std::cout << Target << " is Not Exist.\\n";

	Target = 1;
	isFind = std::binary_search(Nums.begin(), Nums.end(), Target);
	if (isFind)
		std::cout << Target << " is Exist.\\n";
	else
		std::cout << Target << " is Not Exist.\\n";
	
	return 0;
}

17 is Exist.
1 is Not Exist.