PS/Baekjoon Online Judge

[백준 1920] 수 찾기 [C]

kimyoungrok 2021. 7. 15. 23:22

백준 - 1920


풀이

이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다.

이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다.

 

N개의 정수를 Quick Sort로 정렬해준 후, M개의 정수를 입력받음과 동시에 Binary Search로 탐색해 해결했다.

Binary Search의 Big-O는 O(log2n)이지만, n은 최대 100,000으로 재귀 함수로 구현해도 Stack Overflow가 발생하지 않기 때문에 재귀적/비재귀적 방법으로 둘 다 사용 가능하다.


소스코드

#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b){
    int n1 = *(int *)a, n2 = *(int *)b;
    if (n1 < n2)
        return -1;
    else if (n1 > n2)
        return 1;
    return 0;
}
int binary_search(int* arr, int val, int first, int last){
    if (first > last)
        return 0;
    int mid = (first+last) / 2;
    if (val == arr[mid])
        return 1;
    else if (val < arr[mid])
        return binary_search(arr, val, first, mid-1);
    else 
        return binary_search(arr, val, mid+1, last);
}
int main(){
    int N, M, val;
    scanf("%d", &N);
    int arr[N];
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    qsort(arr, N, sizeof(int), compare);
    scanf("%d", &M);
    for (int i = 0; i < M; i++){
        scanf("%d", &val);
        printf("%d\n", binary_search(arr, val, 0, N));
    }
}

출처 및 참고자료

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

이진 탐색 - 나무위키 (namu.wiki)