[백준 1920] 알고리즘 49일차 : 수 찾기

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

1920번: 수 찾기

이분탐색 C++

예 이분탐색 문제입니다

 

정렬 후 이분탐색 끝

놀랍게도 이 쉬운걸 몇번을 틀렸는데요 메모리초과+시간초과가 나왔지만

메모리초과는 로직문제였고 시간초과는..시간단축하는 부가코드 쓰니까 해결

그럼 전 밥을 먹으러 가겠습니다.

요즘은 머리를 쓰기 싫네요. 쉬어가도록하죠

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int num[1000000];

void binarySearch(int key, int n){
    int start = 0;
    int end = n-1;
    int mid;

    while(start <= end){
        mid = (start+end)/2;
        if(num[mid] == key){
            cout << "1\n";
            return;
        }
        else if(num[mid] < key)
            start = mid+1;
        else
            end = mid-1;
    }
    cout << "0\n";
}
int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
    }
    sort(num, num+n);
    int k;
    cin >> k;
    int key;
    for(int i = 0; i < k ; i++){
        cin >> key;
        binarySearch(key, n);
    }
    
    return 0;
}