문제

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

풀이

1. 시간이 많이 짧기 때문에 일반적인 for문으로는 통과가 안된다.
2. 그래서 이진탐색이나 해쉬 맵을 이용해야 하는데 C언어 해쉬 맵 구현은 문제 조건을 보면 어렵기 때문에 이진 탐색 트리를 구현해야 한다.
3. 먼저 이진 탐색을 위해 입력을 받은 뒤 정렬을 진행한다.

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    int int_a = *(int*)a;
    int int_b = *(int*)b;
    if (int_a < int_b) return -1;
    if (int_a > int_b) return 1;
    return 0;
}

int binary_search(int* arr, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return 1;
        } else if (arr[mid] < target) {
            left = mid + 1;  
        } else {
            right = mid - 1; 
        }
    }
    return 0;
}

int main() {
    int N, M;
    
    scanf("%d", &N);
    int *A = (int *)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    
    scanf("%d", &M);
    int *B = (int *)malloc(sizeof(int) * M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &B[i]);
    }

    qsort(A, N, sizeof(int), compare);

    for (int i = 0; i < M; i++) {
        printf("%d\\n", binary_search(A, N, B[i]));
    }

    free(A);
    free(B);

    return 0;
}