(1920) 수 찾기

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

단계별로 풀어보기

25단계(이분 탐색) 1번째

 

 

 

이분 탐색 알고리즘은 정렬된 데이터에서 탐색 범위를 절반씩 줄여나가는 기법이다. 가운데 원소의 값이 찾는 값보다 크거나 같을 때, 반대쪽 구간에는 찾는 값이 있을 가능성이 없으므로 버리고 나머지 구간을 또 절반으로 나누며 찾는 과정이다.

일일히 탐색한다면 O(N)이 걸리지만 이분 탐색은 매 단계마다 구간이 절반으로 줄어드므로 O(log N)이 걸린다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  sort(v.begin(), v.end());
  
  cin >> m;
  
  while(m--){
    int t;
    
    cin >> t;
    
    int idx= lower_bound(v.begin(), v.end(), t)-v.begin();
    
    cout << (idx<n && v[idx]==t) << "\n";
  }
  
  return 0;
}