글 읽기 - c) 퀵소트와 이진탐색

choyj1127 2년 전 0

퀵소트와 이진탐색을 이용하여 구현하였습니다. 어디가 틀린건지 조언 부탁드립니다ㅠ

#include <stdio.h>
#include <stdlib.h>
int arr[100001];
int compare(const void* a, const void* b) {
    return *(int*)a-*(int*)b;
}

int binary_search(int arr[], int first, int last, int target) {
    int mid = (first + last) / 2;
    if (first <= last) {
        if (arr[mid] == target) return 1;
        else if (target < arr[mid])  return binary_search(arr, first, mid - 1, target);
        else return binary_search(arr, mid + 1, last, target);
    }
    return 0;
}

int main() {
    int N; int M;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
    qsort(arr, N, sizeof(int), compare);
    
    scanf("%d", &M); int num;
    for (int i = 0; i < M; i++) {
        scanf("%d", &num); 
        printf("%d\n", binary_search(arr, 0, N - 1, num));
    }
    return 0;
}

sinusoid500 1년 전 0

12번째 줄에 binary_search 함수 들어가실 때 mid - 1 해주셨으면

13번째 줄에 binary_search 함수 들어가실 때 mid + 1이 아닌 mid로 해주시면 될 것 같습니다.

그 반대로 하셔도 되고요.

choyj1127 1년 전 0

그 부분을 놓쳤네요! ㅠㅠ

그렇지만 이진탐색 수정해도 시간초과가 나서.. 병합정렬 이용해서 해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c) 퀵소트와 이진탐색

choyj1127 2년 전 0

sinusoid500 1년 전 0

choyj1127 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말