Так можно ли написать реализацию двоичного поиска, которая возвращает объект вместо индекса? Мне нужно, чтобы вся задача была завершена в O(logn) времени и не тратила больше времени на то, чтобы потом вызвать collection.get() после того, как я получу только индекс, поэтому сложность становится O(nlogn).Реализация бинарного поиска, который возвращает объект вместо индекса?
Для двоичного поиска потребуется контейнер с произвольным доступом. Если вы знаете индекс, вы должны иметь возможность достичь элемента в O (1). Если это не так, тогда двоичный поиск будет неправильным алгоритмом в первую очередь.
В этом случае вы используете ArrayList, который представляет собой оболочку вокруг массива, которая действительно обеспечивает эффективный произвольный доступ.
Вы не будете делать бинарный поиск на что-нибудь но O (1) коллекция произвольного доступа: в противном случае время поиска будет далеко за пределы O (журнал (N)). Так называемое «дополнительное время» не существует в коллекции O (1): ваша замена должна будет сделать тот же шаг в любом случае.
Почему вызов 'get' делает сложность O (nlog (n))? – user2357112
Что это за коллекция? –
@ user2357112, потому что вы разбираете коллекцию серийно, чтобы получить объект, который я предполагаю. Это мотив, как у вас есть указатель на элемент только его индекс в коллекции. –