[PS] Binary Search

BS(이분탐색) 특징

BS의 선행조건은 정렬이 되어있어야 합니다.
BS의 사용하는 상황

1) data가 변하지 않는 상태에서 여러 번 data를 찾아야 하는 경우
2) Data 범위가 너무 큰 경우 -> 시간복잡도 : O(logN)

기본 BS 코드

정해진 수 구하기

#include <iostream>
using namespace std;

int n = 65; // BS로 찾을 n

int main() {

	// 정답 가능 범위
	int left = 1;
	int right = 100;

	while (1)
	{
		int mid = (left + right) / 2;
		if (mid < n)
		{
			left = mid + 1;
		}
		else if (mid > n)
		{
			right = mid - 1;
		}
		else 
		{
			cout << mid;
			return 0;
		}
			
	}
	return 0;
}

정해진 배열 속에서 특정 수 찾기

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

//특정 수 찾기
vector<int> arr = { 1,2,9,10,100,150,240,250,360 };
int n = 240; // 정답

int bs()
{
	int left = 0;
	int right = arr.size() - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else if (arr[mid] > n)
		{
			right = mid - 1;
		}
		else if (arr[mid] == n)
		{
			return mid;
		}
		
	}
	return -1;
}

int main() 
{

	int flag = bs();
	cout << flag<<endl;
	if (flag == -1) cout << "찾는 수 없음\n";
	else cout << flag << "번째의 " << arr[flag] << endl;

	return 0;
}