✔ 문제해결전략
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int target, vector<int>& vec, int len) {
int front = 0;
int end = len - 1;
while(front <= end) {
int mid = (front + end) / 2;
if(vec[mid] > target) end = mid - 1;
else if(vec[mid] < target) front = mid + 1;
else return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
vector<int> num;
cin >> n;
num.resize(n);
for(int i=0;i<n;i++) cin >> num[i];
sort(num.begin(), num.end());
int len = num.size();
cin >> m;
for(int i=0;i<m;i++) {
int t;
cin >> t;
cout << binarySearch(t, num, len) << "\n";
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
vector<int> num;
cin >> n;
num.resize(n);
for(int i=0;i<n;i++) cin >> num[i];
sort(num.begin(), num.end());
cin >> m;
for(int i=0;i<m;i++) {
int k;
cin >> k;
cout << binary_search(num.begin(), num.end(), k) << "\n";
}
}
문제에서 이진 탐색 사용하라고 외치고 있다. std::sort가 nlog(n)이고 binary search가 log(n)인데 m번 하니까 mlog(m) 총 nlog(n) + mlog(n).
while문 조건에 등호 안 넣으면 제대로 동작하지 않는다. front == end인 경우도 생각해 주어야 한다. mid == front == end 우선 된 다음 end가 작아지던지 front가 커지던지 해서 while문 탈출한다
STL binary_search는 오름차순 정렬되어 있을 때만 사용할 수 있다