글 읽기 - 사간초과 c++

kyt0315 1년 전 0

이분탐색으로 잘 짜고 입출력도 잘 넣고 함수 파라미터도 pass by reference 넘겨주는데 시간초과가 뜹니다. 어떻게 해야하나요?

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

void find(vector<int>&a, int n) {
	int left = a[0];
	int right = a[a.size() - 1];

	while (right >= left) {
		int mid = (left + right) / 2;
		if (mid == n) {
			cout << "1\n";
			return;
		}
		else if (mid > n) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout <<"0\n";
	return;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int>a;

	int n;
	int x;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> x;
		a.push_back(x);
	}

	sort(a.begin(), a.end());

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		find(a, x);
	}

	return 0;
}

djm03178 1년 전 1

이분 탐색 로직이 잘못되었습니다. a 내에 수가 들어있는지 찾아야 하는데, 수가 a의 [최소, 최대] 범위 내에 있는지를 보고 있습니다.

kyt0315 1년 전 0

@djm03178

이해했습니다! 정말 감사합니다!

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

문제

문제

출처

ICPC

사간초과 c++

kyt0315 1년 전 0

djm03178 1년 전 1

kyt0315 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말