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

[문제보기]

 1920. 수 찾기

1920번: 수 찾기

 

[풀이과정]

이 문제는 이분탐색 관련한 문제로, 그냥 for문을 통해 탐색을 한다면 시간초과가 나오는 문제이다.

먼저 전처리 과정으로 입력값을 sort()함수를 이용하여 정렬을 하고 난 뒤 이분탐색을 진행한다.

 

solution(int x)가 이분탐색을 하는 함수로, start, end, mid 변수를 사용하여 이분탐색 연산을 진행한다. 

 

[소스코드]

#include <iostream>
#include <algorithm>
using namespace std;
int array[100001] = {0};
int n, m;

void solution(int x){
    int start = 0;
    int end = n-1;
    int mid;

    while(end - start >= 0){
        mid = (start+end)/2;

        if(array[mid] == x){
            cout << "1\n";
            return;
        }

        else if(array[mid] > x){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
    }

    cout << "0\n";
    return;
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> array[i];
    }
    sort(array, array+n);

    cin >> m;
    int x;
    for(int i=0; i<m; i++){
        cin >> x;
        solution(x);
    }

    return 0;
}

 

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