BOJ 1920 c++

BOJ 1920 c++ 수 찾기

백준 1920번 수 찾기 c++

1. STL binary_search를 쓰지 않았을 때.

일치하는 값을 찾으면 1을 출력.

st가 en보다 커지는 경우 못 찾았다는 뜻이므로 0을 출력.

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    int arrN[100005];
    int arrM[100005];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arrN[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> arrM[i];
    //여기까지 입력.

    //binary search start!
    sort(arrN, arrN + n);
    for (int i = 0; i < m; i++) {
        int st = 0;
        int en = n - 1;
        int target = arrM[i];
        while (st <= en) {
            int mid = (st + en)/2;
            if (arrN[mid] < target) {
                st = mid + 1;
            } else if (arrN[mid] > target) {
                en = mid - 1;
            } else {
                cout << 1 << '\n';
                break;
            }
        }
        if (st > en)
            cout << 0 << '\n';
    }
}

2. STL binary_search를 이용.

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    int arrN[100005];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arrN[i];
    cin >> m;
    //여기까지 입력.
    //STL 시작.
    sort(arrN, arrN + n);
    int t;
    for (int i = 0; i < m; i++) {
        cin >> t;
        cout << binary_search(arrN, arrN + n, t) << '\n';
    }
}

binary_search는 arrN ~ arrN + n 의 배열에서 t라는 value를 찾으면 true(1)을, 그렇지 않으면 false(0)을 반환한다.

분류 : 이진 탐색