(알고리즘) 이분탐색

📌이분 탐색이란?

"이분 탐색"은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.

정렬된 배열을 이등분 하여 찾고자 하는 값이 배열의 중앙값보다 작으면 왼쪽 크면 오른쪽을 탐색하는 방식으로 값을 찾습니다.

시간 복잡도는 O(log N)입니다.

---

📌예시 문제

10815_숫자카드

https://www.acmicpc.net/problem/10815

여기서 findCard 부분이 이진 탐색을 행하는 부분입니다.

이진 탐색은 반복문이나 제귀를 통해 구현할 수 있는데
여기서는 반복문을 통해 구현했습니다.

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

int N,M;
vector<int> cards;

int findCard(int card) {
	int left = 0, right = N - 1;
	while (left <= right) {
		int mid = (right + left) / 2;
		if (cards[mid] == card) return 1;
		if (cards[mid] < card) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int n; cin >> n;
		cards.push_back(n);
	}
	sort(cards.begin(), cards.end());

	cin >> M;
	for (int i = 0; i < M; i++) {
		int find; cin >> find;
		cout << findCard(find) << " ";
	}
	return 0;
}