글 읽기 - 이진탐색 알고리즘 질문입니다!! 시간초과문제...

bearsff 2년 전 0

안녕하세요! 두 번째 입력 (M 입력 후 주어지는 입력들)들이 주어진 수들(N 입력 후 주어진 입력들) 중에 있는지 탐색하기 위해 이진탐색을 썼습니다. 아래와 같이 작성하는 문제가 시간초과가 뜨더군요 ㅠㅠㅠㅠ

그래서 이진탐색을

void binarySearch(int l, int r, int num, vector& note1) {
if (l > r) {
printf("0\n");
return;
}
int mid = (l + r) / 2;

if (num == note1[mid])
printf("1\n");
else if (num < note1[mid])
binarySearch(l, mid - 1, num, note1);
else if (num > note1[mid])
binarySearch(mid + 1, r, num, note1);
}

이렇게 바꿨더니 문제가 맞았습니다

둘의 차이는 무엇인가요??? 둘 다 함수 호출 한 번 당 수행하는 비교횟수는 같지 않나요? 둘의 정답여부에 대한 차이가 무엇인지 궁금합니다. 고견 부탁드립니다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void binarySearch(int l, int r, int num, vector<int> &note1) {
	int mid = (l + r) / 2;

	if (num == note1[mid])
		printf("1\n");
	else if (l == r)
		printf("0\n");
	else if (num < note1[mid])
		binarySearch(l, mid - 1, num, note1);
	else
		binarySearch(mid + 1, r, num, note1);
}

int main(void) {
	int T, N, M, num;
	scanf("%d", &T);

	while (T--) {
		vector<int> note1;
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			scanf("%d", &num);
			note1.push_back(num);
		}
		sort(note1.begin(), note1.end());

		scanf("%d", &M);
		for (int i = 0; i < M; i++) {
			scanf("%d", &num);
			binarySearch(0, N - 1, num, note1);
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

이진탐색 알고리즘 질문입니다!! 시간초과문제...

bearsff 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말