[백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬

[백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬

 

하나하나 비교해가면서 풀면 100% 시간초과가 날 것이다.

해당 문제는 이분 탐색의 교과서 같은 문제

 

이분 탐색은 맨 오른쪽, 왼쪽 점을 잡은 뒤 mid 를 정하고 또 이걸 반복해주는 것이다. 

중요한 것은 "정렬"을 해줘야 한다는 점이다.

그래야 12345 라고 쳤을 때 mid인 3보다 목표 숫자가 작으면 그 앞에 있거나 없거나 하고 크면 뒤에 있거나 없거나 하면서 비교해볼 수 있기 때문이다.

 

1) 직접 구현

#include <bits/stdc++.h>

using namespace std;

int n,m, num;
vector<int> v;

int binary_search(int a){
    int r=n-1, l=0;
    while(r>=l){
        int mid = (r+l)/2;
        if(v[mid]==a){
            return 1;
        }
        else if(a>v[mid]){
            l= mid+1;
        }
        else{
            r=mid-1;
        }
    }
    return 0;
}


int main (){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >>n;
    int x;
    for(int i=0; i<n; i++){
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> num;
        cout << binary_search(num) <<"\n";
    }
return 0;
}

 

 

2) STL : binary_search 사용

#include <bits/stdc++.h>

using namespace std;

int main (){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);

    int n,m,num;
    cin >> n;
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
    cin>>m;
    sort(v.begin(), v.end());
    
    while(m--){
        cin >>num;
        cout << binary_search(v.begin(), v.end(),num)<<"\n";
    }
    
    
    
return 0;
}

 

제일 처음 배울 때는 이분 탐색이 정말 어렵게 다가왔는데

다시 보니깐 반띵의 연속인 ..