[백준 1920번] 수 찾기

이진탐색에서 right범위를 맨처음에 100000주고 했는데 33%쯤에서 계속틀렸다.

N-1으로 수정하니 정답.

아무래도 input수가 적을 때 못찾는걸까? 그래서 memset(arr, 0x7f,sizeof(arr))해서 큰값을 주고 시작했는데도..

안되더라.. ㅠ;

시간은 이진탐색 52ms, map 100ms로 2배차이가 난다.

 

이진탐색으로 한 풀이.

#include <bits/stdc++.h>

using namespace std;

map<int,int> m;
int in_array[100001];
int N,M;

bool binary_search(int target)
{
    int left=0,right=N-1, mid;
    
    while(left <= right)
    {
        mid = (left+right)/2;
        if(in_array[mid] == target) return true;
        else if(in_array[mid] <target)
        {
            left = mid+1;
        }
        else
        {
            right = mid-1;
        }
    }
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N ;
    for(int i = 0 ; i<N; i++)
    {
        int temp;
        cin >> temp;
        in_array[i] = temp;
    }
    sort(in_array, in_array+N);
    cin >> M;
    for(int i = 0; i< M; i++)
    {
        int temp;
        cin >> temp;
        if(binary_search(temp))
        {
            cout << 1 << '\n';
        }else{
            cout << 0 << '\n';
        }

    }
}

---

map써서 바로 푼 풀이

#include <bits/stdc++.h>

using namespace std;

map<int,int> m;
int N,M;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N ;
    for(int i = 0 ; i<N; i++)
    {
        int temp;
        cin >> temp;
        m[temp] =0;
    }
    cin >> M;
    for(int i = 0; i< M; i++)
    {
        int temp;
        cin >> temp;
        if(m.find(temp) == m.end())
        {
            cout << 0 << '\n';
        }else{
            cout << 1 << '\n';
        }

    }
}