이진 탐색

phoenixKim·2021년 7월 26일

알고리즘 기법

목록 보기

9/72

이거 하나만 알자!

최우선적으로! 문제에서 제한사항으로 어떠한 키워드의 값이 무한정 클때,
그 키워드를 타겟팅으로 잡고 최소값과 최대값을 만들어서 진행하자.
입국심사 문제

-> 입국심사 기다리는 사람 또는 심사관이 한 명 심사하는데 걸리는 시간을 기준으로 잡자.
카카오 징검다리 건너기 문제

-> stone의 value를 기준으로 잡자.

이진탐색은 언제 해야할까?

1) 탐색범위가 엄청나게 많을 경우 / 1000만 단위 이상의 데이터일 때
2) 정렬시킬수 있거나, 정렬되어 있을때

이진탐색은 코딩테스트에서 빈번하게 나오므로, 외우도록 하자.

반복문으로 접근하자.

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

bool BinarySearch(vector<int>&v, int target)
{
	int start = 0;
	int end = v.size() - 1;

	while (start <= end)
	{
		int mid = (start + end) / 2;

		if (v[mid] == target)
		{
			return true;
		}
		else if (v[mid] < target)
		{
			start = mid + 1;
		}
		else if (v[mid] > target)
		{
			end = mid - 1;
		}


	}


	return false;
}

int main()
{	
	int cnt, target;
	cin >> cnt >> target;

	vector<int>v(cnt, 0);

	for (int i = 0; i < cnt; i++)
	{
		int input;
		cin >> input;
		v[i] = input;
	}

	sort(v.begin(), v.end());


	if (BinarySearch(v, target))
	{
		cout << "찾았다." << endl;
	}
	else
	{
		cout << "못 찾았다." << endl;
	}

}

while문의 부등호에 왜 등호가 포함되는지 항상 궁금했는데, 예제로 해결완료함.

예를 들어서 등호가 없는 상태에서 v = {0,1} , target = 1이라면 not found 이다.

bool BinarySearch(vector<int>&v, int target)
{
	int start = 0;
	int end = v.size() - 1;

	while (start < end)
	{
		int mid = (start + end) / 2;

		if (v[mid] == target)
		{
			return true;
		}
		else if (v[mid] < target)
		{
			start = mid + 1;
		}
		else if (v[mid] > target)
		{
			end = mid - 1;
		}


	}


	return false;
}

왜냐하면 mid값이 0으로 나와서 false로 출력된다.
하지만 등호가 포함된다면 반복문을 한번 더 돌수 있다.
이진 탐색에서의 판별은 for문 내의 조건식에서 하는 거기 때문에
<= 등호를 붙여서 하는 것이 인접한 요소끼리의 반절을 구할때에 대한 value를 구할 수 있다!