[1920] Binary Search

백준 1920번
시간초과 따위 신경쓰지 않았던 나는 문제를 보자마자 무지성 브루트포스 알고리즘으로 코드를 짜면서도 정답률을 보고 무조건 시간 초과가 뜨겠거니 했다. 결과는 예상한 대로...
문제 유형을 보니 이진 탐색이라고 분류되어 있었다. 그렇다면 배열의 원소를 찾는 과정에서 이진 탐색을 통해 시간 복잡도를 감소시키라는 이야기!

1. Binary Search

c++ 내장 함수를 사용해도 상관 없으나 직접 구현해보았다!
LaTeX 쓰는게 재밌어서 psuedocode 열심히 만들어 보았다.

평균적으로 O(log n)의 time-complexity를 갖는다.

2. Solution

#include <iostream>
#include <algorithm>

using namespace std;
bool binary_search(int arr[], int size, int target) { 
  int left = 0;
  int right = size - 1;
  while (left <= right)
  {
    int med = (left + right) / 2;
    if (arr[med] < target) left = med + 1;
    else if(arr[med] > target)
      right = med - 1;
    else
      return true;
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int N = 0;
  cin >> N;
  int integer_list[N];
  for (int i = 0; i < N; i++) {
    cin >> integer_list[i];
  }
  sort(integer_list, integer_list+ N);
  int M = 0;
  cin >> M;
  int check_list[M];
  for (int i = 0; i < M; i++) {
    cin >> check_list[i];
  }
  /*
  for (int i = 0; i < M; i++)
  {
    for (int j = 0; j < N; j++){
      if (check_list[i] == integer_list[j]) {
        cout << 1 << '\n';
        break;
      }
      if (j == N - 1) cout << 0 << '\n';
    }
  }
  */ // O(n^2) search algorithm (brute-force)
  for (int i = 0; i < M; i++)
  {
    if (binary_search(integer_list, N, check_list[i])) cout << 1 << "\n";
    else
      cout << 0 << "\n";
  }
}

3.

메모리 초과가 떴었는데 이는 동적 배열 때문인 것으로 파악하였고, 정적 배열을 쓰니 해결!
시간 초과는 브루트 포스 -> 이진 탐색으로 해결!