글 읽기 - 간단한 질문 드려봅니다.

p_ce1052 4년 전 0

이분탐색할 때 mid에 값이 없으면 start=mide+1 또는 end=mid-1로 잡고 다음 구간에 대해 재귀호출을 했는데 시간초과가 나더라구요. 똑같은 알고리즘으로 while문을 돌렸는데 정답 처리 되었구요. 재귀함수로 짜면 심하게 느려지나요?

int binarysearch(int data,int start,int end){
	int middle=(start+end)/2;
	if(end<start) return 0;
    else if(array[mid]==data) return 1;
    else if(array[mid]<data) return binarysearch(data,mid+1,end);
    else return binarysearch(data,begin,mid-1);
} //재귀함수

int binarysearch(int data,int start,int end){
	int middle=(start+end)/2;
	int begin=start;
	int finish=end;
	while(finish>=begin){
		middle=(finish+begin)/2;
		if(array[middle]==data) return 1;
		else if(array[middle]>data) finish=middle-1;
		else begin=middle+1;
	}
	return 0;
} //개선된 것

djm03178 4년 전 0

느리다고 해도 큰 차이가 아닙니다. 이것만으로는 알 수 없고 전체 코드를 봐야 알 수 있을 것 같습니다.

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

문제

문제

출처

ICPC

간단한 질문 드려봅니다.

p_ce1052 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말