글 읽기 - 제가 이분탐색을 통해서 이 코드를 짯는데 시간초과라고 뜨네요

zoskeksk 7년 전 0

왜 시간초과가 나는 것일까요 보통 이진탐색트리의 경우에대해서 다생각해보고 짯는데

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
#pragma warning(disable:4996)

int divide(vector<pair<int,int> > arr,int start, int end,int key,int index)
{
	if (start <= end)
	{	
		{
			int mid = (start + end) / 2;
			if (arr[mid].first == key && mid != index && arr[mid].second == 0)return mid;
			else if (key < arr[mid].first)
			{
				return divide(arr, start, mid - 1, key, index);
			}
			else
			{
				return divide(arr, mid + 1, end, key, index);
			}
		}
	}
	return -1;
}

int main()
{
	int s;
	int i;
	int key;
	scanf("%d", &s);
	vector<pair<int, int> > a(s);
	scanf("%d", &key);
	for (i = 0; i < s; i++)
	{
		scanf("%d", &a[i].first);
		a[i].second = 0;
	}
	int temp;
	int count = 0;
	sort(a.begin(), a.end());
	for (i = 0; i < s; i++)
	{
		if (a[i].second == 1)continue;
		else
		{
			temp = divide(a, 0, s-1, key-a[i].first,i);
			if (temp == -1)continue;
			else 
			{
				if (a[i].first == key-a[temp].first)
				{
					a[i].second = 1;
					a[temp].second = 1;
					count++;
				}
			}
		}
	}
	printf("%d", count);
}