글 읽기 - 반례 부탁드립니다..

lsch6214 1년 전 0

머릿속에 있는 숫자들 다 넣어보는데도 틀렸다고 하네요.. 조언 따끔하게 받겠습니다. 반례만이라도 찾아주세요...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int binarySearch(int* arr, int target, int start, int end);
void merge(int arr[], int left, int mid, int right);
void mergeSort(int arr[], int left, int right);
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		int N, M, * note_1, * note_2;
		scanf("%d", &N);
		note_1 = (int*)malloc(sizeof(int) * N);
		for (int j = 0; j < N; j++)
			scanf("%d", &note_1[j]);
		mergeSort(note_1, 0, N - 1);
		scanf("%d", &M);
		note_2 = (int*)malloc(sizeof(int) * M);
		for (int j = 0; j < M; j++)
			scanf("%d", &note_2[j]);
		for (int k = 0; k < M; k++)
			printf("%d\n", binarySearch(note_1, note_2[k], 0, N));
		free(note_2);
		free(note_1);
	}
	return 0;
}
int binarySearch(int* arr, int target, int start, int end) {
	int left = start, right = end, mid;
	while (1) {
		mid = (left + right) / 2;
		if (arr[mid] == target || arr[left] == target || arr[right] == mid)
			return 1;
		if (arr[mid] < target)
			left = mid + 1;
		else
			right = mid;
		if (left >= right)
			return 0;
	}	
}
void mergeSort(int arr[], int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
}
void merge(int arr[], int left, int mid, int right) {
	int fldx = left;	int rldx = mid + 1;	int i;
	int *sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sldx = left;
	
	while(fldx <= mid && rldx <= right) {
		if(arr[fldx] <= arr[rldx])
			sortArr[sldx] = arr[fldx++];
		else
			sortArr[sldx] = arr[rldx++];
		sldx++;		
	}
	
	if(fldx > mid) {
		for(i = rldx; i <= right; i++, sldx++)
			sortArr[sldx] = arr[i];
	}
	else {
		for(i = fldx; i <= mid; i++, sldx++)
			sortArr[sldx] = arr[i];
	}
	for(i = left; i <= right; i++)
		arr[i] = sortArr[i];
	free(sortArr);
}

bsheep0304 1년 전 2

반례입니다. 이진 탐색하는 부분 다시 한 번 확인해보세요.

//입력:
1
3
-1 0 1
4
-1000 -2000 3000 4000
//출력:
1
1
0
0
//정답:
0
0
0
0

lsch6214 1년 전 1

말씀대로 이진 탐색 코드에서 문제점을 찾았습니다. . . 감사합니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다..

lsch6214 1년 전 0

bsheep0304 1년 전 2

lsch6214 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말