[백준][C++]1920번 수 찾기

문제

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

1920번: 수 찾기

 

 

풀이

이진 탐색을 적용하면 데이터 정렬까지 고려하여 O(nlogn) 시간 복잡도로 해결할 수 있다.

 

이진 탐색(Binary Search) 알고리즘

이진 탐색(Binary Search) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static int N;
static vector<int> A;

bool binary_search(int num);

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  cin >> N;
  
  A.resize(N);
  for(int i = 0; i < N; i++)
  {
    cin >> A[i];	// 배열 A 저장
  }
  sort(A.begin(), A.end());	// 배열 A 정렬 시간 복잡도: O(nlogn)

  int M;
  cin >> M;

  for(int i = 0; i < M; i++)
  {
    int num;
    cin >> num;

    if(binary_search(num))
    {
      cout << "1\n";
    }
    else
    {
      cout << "0\n";
    }
  }

  return 0;
}

bool binary_search(int num)
{
  int starti = 0;
  int endi = N - 1;

  while(starti <= endi)
  {
    int midi = (starti + endi) / 2;
  
    if(num == A[midi])
    {
      return true;
    }
    else if(num < A[midi])
    {
      endi = midi - 1;
    }
    else if(num > A[midi])
    {
      starti = midi + 1 ;
    }
  }

  return false;
}

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, M;
  cin >> N;
  vector<int> A(N);

  for(int i = 0; i < N; i++)
  {
    cin >> A[i];
  }

  // 배열 A 정렬 시간 복잡도 : O(nlogn)
  sort(A.begin(), A.end());
  cin >> M;

  for(int i = 0; i < M; i++)
  {
    bool find = false;
    int target;
    cin >> target;
    // 이진 탐색 시작
    int start = 0;
    int end = A.size() - 1;

    while(start <= end)
    {
      int midi = (start + end) / 2;
      int midV = A[midi];

      if(midV > target)
      {
        end = midi - 1;
      }
      else if(midV < target)
      {
        start = midi + 1;
      }
      else
      {
        find = true;
        break;
      }
    }
    if(find)
    {
      cout << 1 << "\n";
    }
    else
    {
      cout << 0 << "\n";
    }
  }
  
}