[c++] 백준 1920 - 수 찾기(이진 탐색, 이분 탐색)

0. [c++] 백준  -

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

1. 풀이

이번 문제에서 2개의 배열이 주어지는데, 첫번째 배열은 탐색의 바탕이 되는 배열, 두번째 배열은 탐색을 시행할 수를 담은 배열으로 주어지게 된다.

각각 입력의 최대값(N,M)은 100,000이 되는데, 평소에 하듯 앞에서 부터 탐색을 시행한다면, 최악의 경우 N*M의 탐색을 시행하게 되고, 이 경우 100억의 연산을 필요로 하는, 2초 내에 연산을 하기에는 무리인 크기가 된다.

그럼, 연산을 줄이는 방법은 어떻게 될까?

뭐, 방법이야 많이 존재하겠지만, 이번의 경우에는 이진 탐색이라는 방법을 활용하였다.

이 방법을 활용하기 위해서는, 탐색을 바탕이 되는 첫번째 배열을 오름차순으로 정렬하여야 한다.

이후, 이 함수의 중앙에서 시작하여, 절반씩 쪼개 들어가면서 탐색을 시행하는 것이다.

스무고개를 할 때, 질문을 하면서 점차 정답에 근접하게 질문을 던지는 것 처럼, 이진 탐색도 비슷한데, 탐색을 하는 크기가 매번 절반이 줄어드는 타노스 검색이라 볼 수 있다.

탐색의 범위는 first, last를 이용해 조절하고, 찾는 수가 등장하면 바로 함수가 종료되도록 해주었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include<iostream> #include<algorithm>   using namespace std;   int Arr[100001]; int Arr2[100001];   void binarySearch(const int & N, const int & K) {     int first = 0;     int last = N - 1;     int mid = 1;     while (first <= last) {         mid = (first + last) / 2;         //cout << mid << endl;         if (Arr[mid] == K) {             cout << "1\n";             return;         }         else {             if (Arr[mid] > K)                 last = mid - 1;             else                 first = mid + 1;         }     }     cout << "0\n";     return; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N, M;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> Arr[i];     }     cin >> M;     for (int i = 0; i < M; i++) {         cin >> Arr2[i];     }       sort(Arr, Arr + N);     for (int i = 0; i < M; i++) {         binarySearch(N, Arr2[i]);     }   } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!