[BOJ / C++] 수 찾기 (이분탐색)

문제링크: https://www.acmicpc.net/problem/1920

 

> 방법 1. 직접 구현

1-1. 코드

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

int binarysearch(int target, vector<int>& arr, int n) {
    int st = 0, ed = n-1;
    while (st <= ed) {
        int mid = (st+ed)/2;
        if (arr[mid] == target) return 1;
        else if (arr[mid] < target) st = mid + 1;
        else if (arr[mid] > target) ed = mid - 1;
    }
    return 0;
}

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    while (m--) {
        int inp;
        cin >> inp;
        cout << binarysearch(inp, arr, n) << '\n';
    }
}

 

 

1-2. 분석

binarysearch를 하기전에 정렬을 해줘야한다. target과 arr[mid]를 비교하면서 탐색범위를 절반씩 줄여나간다. 

 

1-3. 시간복잡도

정렬의 시간복잡도 nlgn이고, 실제 이진탐색의 시간복잡도는 lgn이다. n = 10^5이므로 nlgn = 10^6 < 10^8 이므로 시간제한 1초내에 통과가능하다.

 

 

> 방법 2. STL 사용

2-1. 코드

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

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    while (m--) {
        int inp;
        cin >> inp;
        cout << binary_search(arr.begin(), arr.end(), inp) << '\n';
    }
}

 

 

2-2. 분석

stl에 binary_search(arr.begin(), arr.end(), target); 함수가 이미 구현되어있다. 첫번째 인자로 iterator 시작지점, 두번째인자로 iterator 끝지점, 세번째 인자로 찾고자하는 값을 넘겨주면 bool 타입으로 있는지 없는지를 리턴해준다.

 

2-3. 시간복잡도

sort가 nlgn이고 binary_search는 lgn이다. n = 10^5 이므로 nlgn = 10^6 < 10^8 이므로 시간제한 1초내에 통과가능하다.