[C++ 자/알 Note] 이진 탐색

이진 탐색 개념

정렬된 배열 상태에서

처음부터 순회하며 탐색하는 방식이 아닌

재귀적으로 절반을 기준으로 좌/우 중 하나를 선택하여

탐색하는 것을 이진탐색이라고 한다

따라서 시간복잡도는 O(logN)이 걸린다

 

이진 탐색의 문제

배열로 이진탐색을 구현하는 경우는

삽입, 삭제 시 매우 비효율적이다

정렬된 연결리스트는 임의 접근이 불가능하기에

이진탐색 사용이 불가능하다

 

이러한 문제를 해결하기 위해서

배열이나 연결리스트가 아닌 새로운 자료구조인

트리 구조를 이진탐색과 함께 이용한다

 

이진 탐색 구현 with 배열

vector<int> numbers;

void BinarySearch(int N)
{
	int left = 0;
	int right = (int)numbers.size() - 1;

	while (left <= right)
	{
		cout << "탐색 범위: " << left << "~" << right << endl;

		int mid = (left + right) / 2;

		if (N < numbers[mid])
		{
			cout << N << " < " << numbers[mid] << endl;
			right = mid - 1;
		}
		else if (N > numbers[mid])
		{
			cout << N << " > " << numbers[mid] << endl;
			left = mid + 1;
		}
		else
		{
			cout << "찾음!" << endl;
			break;
		}
	}

}