[ 백준 1920 ] 수 찾기 (C++)

[문제보기]

 

[해결과정]

 1. 수 입력 받기.

 2. 오름차순 정렬 (sort)

 3. 문제 입력 받기 ( 입력 받고 바로 결과 값 도출)

 4. 이분 탐색 활용

 5. 이분 탐색은 값을 기준이 아닌 배열의 idx 값을 기준으로 이분 탐색 시행

 

[소스코드]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<memory.h>
#include<cstring>
using namespace std;
 
int arr[100001];
int n,m;
 
bool ans;
 
void search(int s, int e, int find) {
    if (ans == true) return;
    if (s > e) return;
 
 
    int mid = (s + e) / 2;
    if (arr[mid] == find) {
        ans = true;
        return;
    }
    
    if (arr[mid] >= find) {
        e = mid;
        search(s, mid-1, find);
    }
    else {
        s = mid;
        search(mid+1, e, find);
    }
 
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    cin >> m;
 
    for (int i = 0; i < m; i++) {
        ans = false;
        int temp;
        cin >> temp;
        search(0, n - 1, temp);
        if (ans == 1) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
 
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 이분 탐색은 사실 겁 먹어서 구현을 피해왔던 문제였는데, 오늘 공부하며 완벽하게 숙지했다. 실수 한 부분은 s와 e에 mid값을 계속 저장했는데, 그럴 필요없이 매개 변수에 mid+1, mid-1 식으로 하면 간단했다는 거 정도!

 

[관련 문제 혹은 비슷한 문제]

 이분 탐색