1920번 - 수 찾기(c++)

🗒 1920번 문제

📌 이진 검색 알고리즘을 사용해서 수를 찾자 ❗️

1️⃣ 일반 for문을 사용해서 수를 찾을 경우, '시간 초과'가 발생 -> binary Search 사용하자

2️⃣ 이진 검색 알고리즘이란? 
'오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘' 
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택

3️⃣ 정렬된 첫 번째 array와 두 번째 array를 비교한다 -> binary Search를 사용하여

4️⃣ low값보다 high값이 작을 때까지 loop를 돌면서 두 번째 array 원소와 같은 걸 찾는다

5️⃣ low, high, mid 사용해서 key 값 비교 -> 없으면 0, 있으면 1 return

➰ 코드로 나타낸 1920번 ➰

#include <cstdio>
#include <algorithm>

using namespace std;

int firstArr[100001];
int secondArr[100001];

int binarySearch(int num, int key) {
   int low = 0, high = num - 1, mid;
   
   while (low <= high) {
       mid = (low + high) / 2;
       
       if (firstArr[mid] == key)
           return 1;
       else if (firstArr[mid] > key)
           high = mid - 1;
       else
           low = mid + 1;
   }
   return 0;
}

int main() {
   int fnum = 0, snum = 0;
   
   scanf("%d", &fnum);
   for (int i = 0; i < fnum; i++)
       scanf("%d", &firstArr[i]);
   
   scanf("%d", &snum);
   for (int i = 0; i < snum; i++)
       scanf("%d", &secondArr[i]);
   
   sort(firstArr, firstArr+fnum);
   
   for (int i = 0; i < snum; i++) {
       if (binarySearch(fnum, secondArr[i]))
           printf("1\n");
       else
           printf("0\n");
   }
   return 0;
}