백준 1920 - 수 찾기
백준 1920 - 수 찾기문제 풀이범위 1~10만개의 숫자들 중에서 M개의 주어진 값이 존재하는지 확인하는 문제이다. 일반적인 탐색을 진행할 경우 O(N*N)의 시간복잡도를 갖게 되므로 O(logN)의 시간복잡도를 갖는 이분 탐색을 이용해 문제를 해결하도록 한다. 전체 소스#include <bits/stdc++.h>using namespace std;int binarySearch(vector<int>& arr, int value) { int begin = 0; int end = arr.size() - 1; while (begin <= end) { int mid = (begin + end) / 2; int midValue = arr[mid]; if (value == midValue) { return 1; } else if (value > midValue) { begin = mid + 1; } else { end = mid - 1; } } return 0;}vector<int> solution(vector<int> arr, vector<int> values) { vector<int> results; for (int valuesIndex = 0; valuesIndex < values.size(); valuesIndex++) { int result = binarySearch(arr, values[valuesIndex]); results.push_back(result); } return results;}int main(void) { int n, m; vector<int> arr; vector<int> values; cin >> n; arr = vector<int>(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr.begin(), arr.end()); cin >> m; values = vector<int>(m); for (int i = 0; i < m; i++) { cin >> values[i]; } vector<int> results = solution(arr, values); for (int value : results) { cout << value << '\n'; } return 0;}