글 읽기 - 1920 번 c언어 질문입니다.

purpose 6년 전 0

반례가 어떤게 있을까요?? 여러가지 돌려봤는데 못찾겠네요..ㅜㅠ

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

int Msort(int *arr, int len);
int BinarySearch(int *arr, int size, int findData);

int main(){
    int i;
    int n, m;
    scanf("%d", &n);
    int *arr;
    arr = (int *)malloc(n*sizeof(int)); // 동적할당
    for(i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    Msort(arr, sizeof(arr));
    scanf("%d", &m);
    int *Farr;
    Farr = (int *)malloc(m*sizeof(int)); // 동적할당
    for(i = 0; i < m; i++){
        scanf("%d", &Farr[i]);
        printf("%d\n", BinarySearch(arr, sizeof(arr), Farr[i]));
    }
}

int Msort(int *arr, int len){
    if(len < 2) return 0;
    
    int mid = len / 2;
    Msort(arr, mid);
    Msort(arr + mid, len - mid);
    int *buf;
    buf = (int *)malloc(sizeof(int)*len);
    int i = 0;
    int j = mid;
    int k = 0;
    while(i < mid && j < len)
        buf[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    while(i < mid)
        buf[k++] = arr[i++];
    while(j < len)
        buf[k++] = arr[j++];
    
    for(i = 0; i < len; i++){
        arr[i] = buf[i];
    }
}

int BinarySearch(int *arr, int size, int findData){
    int mid;
    int left = 0;
    int right = size - 1; // 배열 마지막 값을 가진 index는 size - 1 이다.
    while(left <= right){
        mid = (left + right) / 2;
        if(findData < arr[mid]) right = mid - 1;
        else if(findData > arr[mid]) left = mid + 1;
        else return 1;
    }
    return 0;
}