# 백준 : 수 찾기(1920)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1920_findingnumber)

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

int basket[100001];
int outter[100001];

bool findnumber(int left, int right, int number) {
    bool    result;
    int     center = (left + right)/2;
    
    if(left > right) return false;
    else {
        if(basket[center] > number) {
            result = findnumber(left, center-1, number);
        }
        else if(basket[center] < number) {
            result = findnumber(center+1, right, number);
        }
        else {
            return true;
        }
        return result;
    }
}

int main(void) {
    int number, inputcount, findcount;
    
    cin>>inputcount;
    for(int i=0; i<inputcount; i++) {
        cin>>basket[i];
    }
    sort(basket, basket + inputcount);
    
    cin>>findcount;
    for(int i=0; i<findcount; i++) {
        cin>>outter[i];
    }
    
    for(int i=0; i<findcount; i++) {
        if(findnumber(0, inputcount-1, outter[i])) cout<<"1\n";
        else                                    cout<<"0\n";
    }
    return 0;
}

풀이

이진탐색을 사용하는 문제인데, 아이디어를 떠올리는 것은 쉬웠지만 마지막 종료 조건을 생각하는 것이 약간 힘들었다. 연속된 배열에서 중간 지점을 잡고, 그 중간 지점을 기준으로 검색하고자 하는 숫자가 더 크다면 오른쪽으로, 작다면 왼쪽으로 계속 중간지점을 옮겨가면서 검색하는 방식이다.
이게 끝까지 가다보면 왼쪽의 인덱스가 오른쪽의 인덱스보다 커지는 경우가 발생한다. 즉 '열심히 뒤지고 찾고 뚫어지게 쳐다봤는데 결국 아무것도 안나왔다!'는 의미인데, 이 경우 false를 출력하면 된다.
이번 문제에서 새롭게 알게 된 사실은 '배열도 Algorithm 헤더에 있는 sort 함수를 사용할 수 있다'는 것이다. 나는 벡터에서만 사용할 수 있는 줄 알았는데 얼마나 감사하던지.. 
배열에서 sort를 사용하려면, sort(배열이름, 배열이름 + 배열크기)로 사용하면 된다.

한가지 궁금한점은, 처음에 구현한 방식은 검색하고자 하는 숫자를 입력받자마자 곧바로 findnumber로 결과를 도출하는 방식이었는데 이 경우 시간 초과가 발생했었다. 그런데 숫자를 모두 입력받고 한번에 findnumber로 연속된 검색을 진행했을때는 시간 초과가 발생하지 않았다.. 이건 왜 그럴지 좀 생각해보아야겠다.