글 읽기 - c++ 시간초과 질문

seungho0510 3년 전 0

c++질문이요 머지소트랑 이분탐색으로 구현했는데 왜 시간초과가 날까요?

#include <iostream>

int mArr[10000001];
int  arr[10000001];
void merge(int arr[],int start,int mid,int end){
	int i=start;
	int j=mid+1;
	int k = start;
	while(i<=mid && j<=end){
		if(arr[i]<arr[j]){
			mArr[k] = arr[i];
			i++;
		}
		else{
			mArr[k] = arr[j];
			j++;
		}
		k++;
	}
	int t;
	if (i>mid){
		for (t=j; t<=end; t++){
			mArr[k] = arr[t];
			k++;
		}
	}
	else{
		for(t=i; t<=mid; t++){
			mArr[k] = arr[t];
			k++;
		}
	}

	for(t=i; t<j; t++){
		arr[t] = mArr[t];
	}
}

void merge_sort(int arr[], int start,int end){
	if (start<end){
		int mid = (start+end)/2;
		merge_sort(arr,start,mid);
		merge_sort(arr,mid+1,end);
		merge(arr,start,mid,end);
	}
}
int bin_search(int start,int end,int find){
	int i=start;
	int j=end;
	int mid = (start+end)/2;
	while(i<=j){
		int mid = (i+j)/2;

		if (find==arr[mid]){
			return 1;
		}
		else if(find<arr[mid]){
			j=mid-1;
		}
		else if(find>arr[mid]){
			i=mid+1;
		}
		
	}
	return 0;
}

int main(){

	int i,n,el;
	std::cin >> n;

	for (i=0; i<n; i++){
		std::cin>>el;	
		arr[i] = el;
		
	}
	merge_sort(arr,0,n-1);

	std::cin>>n;
	for (i=0; i<n; i++){
		std::cin>>el;
		std::cout<<bin_search(0,n-1,el)<<" ";
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

c++ 시간초과 질문

seungho0510 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말