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

이분 탐색(Binary Search)

 

이분 탐색이란?

 

 - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다.

 

 - 순차 탐색 보다 훨씬 좋은 성능을 보인다.

 

 - n개의 데이터가 주어지면 O(logn)의 시간복잡도를 가진다.

 

 - 데이터를 절반씩 나누어 가며 탐색한다.

 

---

 

이분 탐색 과정

 

 - 1. 데이터의 중앙 값과 찾는 값을 비교한다.

 

 - 2-1. 찾는 값 > 중앙 값인 경우 중앙 값의 오른쪽 부분을 탐색한다.

   2-2. 찾는 값 < 중앙 값인 경우 중앙 값의 왼쪽 부분을 탐색한다.

   2-3. 찾는 값 = 중앙 값인 경우 탐색을 종료한다.

 

 - 3. 2의 과정에 의해 얻은 탐색 부분에 다시 1~2번 과정을 반복해서 탐색한다.

 

 - 예시(22 찾기)

1. 정렬된 데이터

 

2. Left와 Right의 중간 원소인 Mid의 값(31)과 찾는 값(22)을 비교한다.

 

3. 2번 과정에 의해서 얻은 새로운 탐색 부분에서 다시 Mid를 구하고, 해당 값(11)과 찾는 값(22)을 비교한다.

 

 

 

4. 3번 과정에 의해서 얻은 새로운 탐색 부분에서 다시 Mid를 구하고, 해당 값(22)과 찾는 값(22)을 비교한다.

 

5. Mid의 값(22)과 찾는 값(22)이 일치하면 값을 찾은 것이다.

 

 - Left위치 > Right위치가 되면, 값을 찾지 못한 것이다.

 

 

---

 

이분 탐색 코드(C++)

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& v,int target)
{
	// left는 첫 인덱스
	int left = 0;
	// right는 마지막 인덱스
	int right = v.size()-1; 
	int mid;

	while (left <= right)
	{
		mid = (left + right) / 2;

		// 탐색 완료한 경우 해당 인덱스 반환
		if (target == v[mid])
			return mid;
		else
		{
			// 중간 값이 더 큰 경우 중간 값 왼쪽 부분을 탐색하기 위해 right 값을 설정한다.
			if (target < v[mid])
				right = mid - 1;
			// 중간 값이 더 작은 경우 중간 값 오른쪽 부분을 탐색하기 위해 left 값을 설정한다.
			else
				left = mid + 1;
		}
	}

	// 탐색에 실패한 경우(값이 존재하지 않는 경우)
	return -1;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v{ 7,10,11,22,27,31,33,40,45,49,60 };

	cout << "22 탐색 결과 인덱스 : " << binarySearch(v, 22) << endl;
	cout << "50 탐색 결과 인덱스 : " << binarySearch(v, 50) << endl;


	return 0;
}

 

실행 결과