백준 1920번: 수 찾기 (Python, C++)

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

1920번: 수 찾기

---

Level: Silver IV

Solved By: Binary Search

 

기존 이분 탐색에 대한 감을 잃지 않기 위해 풀어본 문제였습니다.

이분 탐색을 위해서는 탐색을 진행하는 배열에 대해 정렬이 되어 있어야 하며,

현재 mid index에 해당하는 value가 찾고 있는 find value보다 작거나 큰 경우에 어떻게 처리를 하는가가 이분 탐색의 핵심입니다.

아래의 코드와 같이 high를 mid-1로 잡아서 탐색 영역을 반으로 줄이거나 low를 mid+1로 잡아서 탐색 영역을 반으로 줄여가며, 탐색할 수 있습니다.

Python

N = int(input())
n = list(map(int, input().split()))

M = int(input())
m = list(map(int, input().split()))

n.sort()

for find_value in m:
    low = 0
    high = len(n)-1
    flag = False
    
    while low <= high:
        mid = int((low+high)>>1)
        
        if find_value < n[mid]:
            high = mid - 1
        elif find_value > n[mid]:
            low = mid + 1
        else:
            flag = True
            break
    print((1 if flag == True else 0))

C++

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

int N, M;
vector<int> n, m;

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int a; cin >> a;
        n.push_back(a);
    }
    
    cin >> M;
    for(int i = 0; i < M; i++){
        int a; cin >> a;
        m.push_back(a);
    }
    
    sort(n.begin(), n.end());
    
    for(auto find_value:m){
        int low = 0, high = n.size()-1;
        bool flag = false;
        while(low <= high){
            int mid = (low+high) >> 1;
            
            if(find_value < n[mid]){
                high = mid - 1;
            }
            else if(find_value > n[mid]){
                low = mid + 1;
            }
            else{
                flag = true;
                break;
            }
        }
        cout << flag << '\n';
    }
    return 0;
}