[#12] Binary Search : 이진 탐색

이진 탐색

이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 고속 탐색 알고리즘중 하나이다. 

 

이진 탐색 순서

1. 데이터 집합의 중앙에 있는 요소를 선택한다.
2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교한다.
3. 중앙 요소값보다 작으면 중앙 기준으로 왼쪽, 그 반대면 오른쪽을 재 탐색한다.
4. 데이터 집합의 마지막 인덱스까지 1~3번을 반복한다.

 

 

---

 

코드

 

백준에 있는 다음 문제를 이진 탐색으로 풀었다.

 

코드

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

void Input(int& v) { cin >> v; }
void Output(int& v) { cout << v << ' '; }
bool BinarySearch(vector<int>& Base, int Target);

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

	int n = 0;  // 상근이가 가지고 있는 카드의 수
	int m = 0;  // 숫자 카드에 적혀있는 수

	// 상근이 카드 입력 받기
	cin >> n;
	vector<int> card(n);
	for_each(card.begin(), card.end(), Input);
	
	// 숫자 카드에 적혀 있는 수 입력 받기
	cin >> m;
	vector<int> demo(m);
	for_each(demo.begin(), demo.end(), Input);

	// 탐색 전 오름차순 정렬
	sort(card.begin(), card.end(), less<>());

	// 이진 탐색으로 값 찾기 
	for (int i = 0; i < demo.size(); i++)
		cout << BinarySearch(card, demo[i]) << ' ';

	return 0;
}

bool BinarySearch(vector<int>& Base, int Target)
{
	int  left = 0, mid = 0, right = 0;
	left = 0;
	right = Base.size() - 1;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (Target == Base[mid])
			return true;
		else if (Target < Base[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
	return false;
}

 

---