글 읽기 - [C언어] 이진탐색/퀵정렬, 시간초과

comfortindex 2년 전 0

이진탐색과 qsort로 코드를 짜 보았는데 계속 시간초과가 뜹니다. 어느 부분에서 그런건지 저는 잘 파악이 안되네요ㅠㅜ

선생님들의 지혜를 나누어 주시면 매우 감사허겠습니다...

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

int binary_search(const int arr[], int size, int key)
{
    int left = 0;
    int right = size - 1;
    int mid;
    while(left < right)
    {
        mid = (left + right) / 2;
    
        if(arr[left] == key || arr[mid] == key || arr[right] == key)
            return 1;
        else if(arr[mid] < key)
            left = mid + 1;
        else // arr[mid] > key
            right = mid + 1;
    }
    return 0;
}

int cmp (const void *a, const void *b)
{
    return *(int *)a > *(int *)b ? 1 : *(int *)a < *(int *)b ? -1 : 0;
}

int main (void)
{
    int i, N, M;

    scanf("%d", &N);
    int *input = (int *)malloc(N * sizeof(int));
    for(i=0; i < N; i++)
        scanf(" %d", &input[i]);

    scanf("%d", &M);
    int *target = (int *)malloc(M * sizeof(int));
    for(i=0; i < M; i++)
        scanf(" %d", &target[i]);

    qsort(input, N, sizeof(int), cmp);

    for(i=0; i < M; i++)
        printf("%d\n", binary_search(input, N, target[i]));

    free(input);
    free(target);
    return 0;
}

index 2년 전 1

else if(arr[mid] < key)

left = mid + 1;

left = mid - 1이 돼야 맞지 않을까요?

comfortindex 2년 전 0

선생님 너무 감사드립니다...

지금 저를 매우 때리고 있습니다...

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

문제

문제

출처

ICPC

[C언어] 이진탐색/퀵정렬, 시간초과

comfortindex 2년 전 0

index 2년 전 1

comfortindex 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말