글 읽기 - C++ 이진탐색 시 시간 초과

yusu218 1년 전 0

lower_bound로 해결하긴 했는데, 저의 이진 탐색 알고리즘은 어디가 문제길래 자꾸 시간 초과가 나는 걸까요?

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

void quickFind(std::vector<int>& list, int i, int j, int val, int& res)
{
	if (j - i > 1)
	{
		int half = (j - i) / 2;
		if (val <= list[half])
			quickFind(list, i, half, val, res);
		else
			quickFind(list, half+1, j, val, res);
	}
	else
		res = (i == j || val == list[i]) ? i : j;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;
	
	std::vector<int> arr(n);
	for (int i = 0; i < n; ++i) std::cin >> arr[i];
	
	auto uniqueArr = arr;
	std::sort(uniqueArr.begin(), uniqueArr.end());
	uniqueArr.erase(std::unique(uniqueArr.begin(), uniqueArr.end()), uniqueArr.end());

	for (int i = 0; i < n; ++i)
	{
		int id;
		quickFind(uniqueArr, 0, uniqueArr.size() - 1, arr[i], id);
		std::cout << id << " ";
	}
	std::cout << "\n";

	return 0;
}

djm03178 1년 전 1

half가 (j - i) / 2가 아니라 i + (j - i) / 2가 되어야 합니다.

yusu218 1년 전 0

뜻밖의 멍청한 실수였네요...! 감사합니다!

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

문제

문제

출처

ICPC

C++ 이진탐색 시 시간 초과

yusu218 1년 전 0

djm03178 1년 전 1

yusu218 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말