백준 1920번(수 찾기) 풀이

문제

입력

출력

 

 

해결방법

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

vector<int> a;

int findnum(int num, int left, int right) {
    int index = (left + right) / 2 + (left + right) % 2;

    if (num == a.at(index) || right + left == 1 && num == a.at(left) || right - left == 1 && num == a.at(right)) {
        return 1;
    }
    else if (right + left == 1 && num != a.at(left) || right - left == 1 && num != a.at(right)) {
        return 0;
    }

    if (num > a.at(index)) {
        return findnum(num, index, right);
    }
    else if (num < a.at(index)) {
        return findnum(num, left, index);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, num, m;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> num;
        a.push_back(num);
    }

    sort(a.begin(), a.end());

    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> num;
        cout << findnum(num, 0, n - 1) << '\n';
    }
}

 

입력을 받고 이진탐색을 위해 오름차순 정렬을 한다.

그 후 이진탐색을 진행하는 findnum이라는 함수를 생성해 준다.

 

배열의 가운데 있는 수를 비교해

내가 찾는 수가 맞으면 1을 리턴 

 

아닐 경우에는 다시 찾는다.

내가 찾는 수가 가운데 있는 수보다 클 때는 가운데를 기준으로 오른쪽 배열을 다시 탐색

가운데 있는 수보다 작을 때는 가운데를 기준으로 왼쪽 배열을 다시 탐색한다.

 

이렇게 탐색을 하다가

끝까지 탐색을 했는데도 없을 경우에는 0을 리턴해줬다