이진 탐색

STL 에서 이진탐색을 제공하고 있음

이진 탐색(binary search)

배열에 데이터가 정렬되어 있을 때 

 

탐색 자체는 O(logn) 이다. 빠름

 

특정 숫자가 배열에 있는지 찾는다면,

배열의 중간 배열부터 시작해서 탐색한다.

 

정렬되어 있는 배열을 배열의 중간 인덱스로 재귀 속성을 가지고 탐색한다.

정렬된 연결 리스트로는 불가하다. [] 를 이용한 임의 접근이 불가능해서임

 

배열 자체가 중간 삽입/삭제가 느리기 때문에 해당 값의 인덱스를 찾아도 거기서 해당 값을 삭제하거나 없을 시 삽입 하면 그때는 시간복잡도 O(n) 으로 느리게 반응하는 단점이 생긴다.

 

그래서 데이터의 변경까지 빠르게 하기 이해서 이진 탐색 트리를 사용한다.

밑은 이진 탐색을 반복문과 재귀로 구현한 것

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> numbers;

// 몇 번째에 위치하는지 반환
int BinarySearch(int n)
{
	int left = 0;
	int right = numbers.size() - 1;

	// left right = 0 일 때 혹은 size 일때 마지막까지 봐야해서 <=
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (n > numbers[mid])
		{
			left = mid + 1;
		}
		else if (n < numbers[mid])
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return numbers.size();
}

// 재귀
int BinarySearch2(int n, int l, int r)
{
	if (l > r)
	{
		return numbers.size();
	}
	int left = l;
	int right = r;
	int mid = (left + right) / 2;

	if (n == numbers[mid])
	{
		return mid;
	}

	if (n < numbers[mid])
	{
		BinarySearch2(n, left, mid - 1);
	}
	else
	{
		BinarySearch2(n, mid + 1, r);
	}

	
}

int main()
{
	numbers = vector<int>{ 1,2,3,4,5,6,7,8,9,10,11,12 };
	//cout << BinarySearch(12) << endl;
	cout << BinarySearch2(14, 0, numbers.size() - 1) << endl;



	return 0;
}