[BOJ] 1920번: 수 찾기

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

1920번: 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

풀이

📙이분 탐색(Binary Search)

탐색범위를 절반 씩 줄여나가면서 값을 찾는 알고리즘이다.

이분 탐색하기 위해 우선 입력받은 숫자 배열을 오름차순으로 정렬한다.

start는 배열의 첫 번째, end는 배열의 마지막, mid는 start와 end의 중간 index라 하자.

start가 end 위치를 넘어가기 전까지 반복문을 실행하여

배열의 mid번째 원소가 찾으려는 값과 같다면 탐색을 끝낸다.

만약 찾으려는 값이 배열의 mid 번째 원소보다 크다면 mid+1부터 end까지를 다시 탐색하고,

mid 번째 원소보다 작다면 start부터 mid-1 까지를 다시 탐색한다.

 

코드

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

int n;
int arr[100001] = {0,};

// 이분탐색
void search(int x) {
  int start = 0;
  int end = n-1;
  int mid;

  while(end >= start) {
    mid = (start+end)/2;
    if(arr[mid] == x) {
      cout << "1\n";
      return;
    }
    else if(arr[mid] > x) {
      end = mid-1;
    }
    else {
      start = mid+1;
    }
  }
  cout << "0\n";
  return;
}

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

  int a, m, b;
  cin >> n;

  
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+n);

  cin >> m;
  for(int i = 0; i < m; i++) {
    cin >> b;
    search(b);
  }
}

숫자를 입력받아 배열에 해당 인덱스 번호가 있을 경우 그 위치에 1을 넣어 그 숫자가 있는지 없는지 확인하려 했는데 입력받을 수 있는 수의 범위가 -2³¹ ~ 2³¹ 이므로 배열을 선언할 수 없어 이 방법은 적합하지 않았다. 

 

결과