BOJ 1920 수 찾기

boj 1920 수 찾기

예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 en은 14가 있을 수 있는 범위의 처음과 끝 인덱스를 의미한다. mid는 (st+en)/2 이다. A[mid]와 14의 값을 비교하며 st와 en의 값을 계속 바꿔나갈 것이다.

• 만약 A[mid] > 14 이면, 14는 mid와 en 사이에 있음이 자명하고, 그러므로 st = mid+1 이라고 할 수 있다.
• 만약 A[mid] < 14 이면, 14는 st와 mid 사이에 있음이 자명하고, 그러므로 en= mid-1 이라고 할 수 있다.
• 만약 A[mid] = 14 이면, mid 값을 반환한다.

찾고자 하는 값이 A 안에 있다면, 위와 같은 과정을 거쳐서 A[mid] = target 이 된다. 이 때, target이 A 안에 없다면 en < st가 될 것이다. 이렇게 되면 함수를 종료하고 -1을 반환한다.

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

int N;
int M;
int A[100005];

int BinarySearch(int target, int length)
{
    int st = 0;
    int en = length - 1;

    while (st <= en)
    {
        int mid = (st + en) / 2;
        if (A[mid] < target) st = mid + 1;
        else if (A[mid] > target) en = mid - 1;
        else return mid;
    }
    return -1;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);
    cin >> M;

    while (M--)
    {
        int target;
        cin >> target;

        if (BinarySearch(target, N) == -1) cout << '0' << '\n';
        else cout << '1' << '\n';
    }
}