글 읽기 - c언어 이진탐색 시간초과가 왜 뜨는 건가요??

heesuk9898 3년 전 0

알고리즘이 잘못되었나요??

#include <stdio.h>

int binsearch(int *arr, int len, int answer)
{
	int l = 0;
	int r = len-1;
	int m;
	while(l<=r)
	{
		m = l+(r-l)/2;
		if(arr[m]==answer)
			return 1;
		else if(arr[m]<answer)
			l=m+1;
		else if(arr[m]>answer)
			r=m-1;
	}
	return -1;
}

int sorting(int *arr, int len)
{
	int i,j;
	int temp;
	for(i=0;i<len;i++)
	{
		for(j=0;j<len-i-1;j++)
		{
			if(arr[j]>arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}


int main()
{
	int num,i;
	scanf("%d",&num);
	
	int numarr[num];
	for(i=0;i<num;i++)
	{
		scanf("%d",&numarr[i]);
	}
	sorting(numarr,num);
	
	int datacnt;
	scanf("%d",&datacnt);
	int data;
	int resarr[datacnt];
	for(i=0;i<datacnt;i++)
	{
		scanf("%d",&data);
		if(binsearch(numarr,num,data) == 1)
			resarr[i]=1;
		else
			resarr[i] = 0;
		
	}
	
	for(i=0;i<datacnt;i++)
	{
		printf("%d\n",resarr[i]);
	}
	
	return 0;
}

nahwasa 3년 전 0

sorting이 현재 O(N^2)으로 되어있습니다.

그리고 N은 최대 10만개죠!

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

문제

문제

출처

ICPC

c언어 이진탐색 시간초과가 왜 뜨는 건가요??

heesuk9898 3년 전 0

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말