백준 1920 (수 찾기) / C++

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

문제 링크입니다.

 

 

> 풀이

N개의 정수 배열을 M번 탐색하는 문제입니다. 탐색 알고리즘은 크게 2가지가 있는데, 순차탐색과 이진탐색입니다.

 

순차탐색을 선택하여 문제를 풀 경우 시간복잡도 O(N * M)으로 최대 연산 횟수가 10만 * 10만이 됩니다. --> 보통 시간제한 1초당 연산 횟수 1억번으로 가정하는데, 순차탐색을 사용할 경우 시간 제한을 넘기게 됩니다.

 

이진탐색을 선택하여 문제를 풀 경우 시간복잡도 O(N * logM)으로 제한시간 이내로 연산을 수행할 수 있을 것입니다.

따라서 이진탐색을 사용하여 구현합시다.

(이진 탐색을 사용할 경우, N 배열을 정렬해 주어야 합니다.)

 

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

int bSearch(int N, int key);

int arrN[100001];
int arrM[100001];

int main() {
   int M, N;
   
   scanf("%d", &N);
   for (int i = 0; i < N; i++)
      scanf("%d", &arrN[i]);

   scanf("%d", &M);
   for (int i = 0; i < M; i++)
      scanf("%d", &arrM[i]);

   sort(arrN, arrN + N);

   for (int i = 0; i < M; i++) {
      if (bSearch(N, arrM[i]))
         printf("1\n");
      else
         printf("0\n");
   }

   return 0;
}

int bSearch(int N, int key) {	//참이면 1, 거짓이면 0
   int low = 0;
   int high = N - 1;
   int mid;

   while (low <= high) {
      mid = (low + high) / 2;

      if (arrN[mid] == key) 
         return 1;
      else if (arrN[mid] > key)
         high = mid - 1;
      else
         low = mid + 1;
   }
   return 0;
}

(개발 환경 : MS Visual Studio 2019)