Означает ли это бинарный алгоритм поиска?

Мне нужно написать небольшую программу Java, чтобы узнать, сколько времени требуется для выполнения алгоритма поиска.Означает ли это бинарный алгоритм поиска?

Алгоритм гласит:

Предположим, у вас есть алгоритм поиска, который на каждом уровне рекурсии, исключающую половину данных из рассмотрения при поиске конкретного элемента данных. Поиск останавливается только при оставлении одного элемента данных.

Я хотел бы знать ваше мнение о том, какой алгоритм поиска он есть.

источник

2015-03-14 1011

Это алгоритм двоичного поиска, да. Однако, по-видимому, существует более чем один алгоритм, который делает это. Я уверен, что кто-то может придумать какой-нибудь фантастический алгоритм, который найдет способ исключить половину его ввода на каждом шагу и не будет функционировать, как это делает обычный бинарный поиск. –

Информация, предоставленная в вопросе, недостаточна. Ответ зависит от того, как точно исключена половина данных. – kraskevich

Вот что меня беспокоит. Это то, что упоминается в статье для задачи, с которой я работаю. Если данные будут вставлены случайным образом, было бы очень сложно найти его именно так. Поэтому мой вывод заключался в том, что это был двоичный поиск. – 1011

звучит как бинарный поиск или половину интервала поиска при условии, что ваша коллекция или сортировки данных, худший и everage случай O(log n)

если придется сортировать первый, то лучший алгоритм даст вам O (N log n), затем плюс O (log n) двоичного поиска, в целом это становится O(n log n)

источник

2015-03-14 13:53:23 iamiddy

Спасибо. На самом деле мне нужно найти время, необходимое для поиска определенного элемента, когда число экспоненциально возрастает – 1011

Если ваши данные отсортированы, то да, это алгоритм двоичного поиска. Этот алгоритм входит в стратегию «Divide and Conquer». При этом каждый раз алгоритм переходит к делению данных, и половина данных исключается. Основное предположение - данные сортируются перед применением алгоритма.

источник

2015-03-14 13:48:06

, что означало бы его алгоритм бинарного поиска. Что меня беспокоит, так или иначе можно использовать «этот алгоритм» на случайных данных, то есть данные не сортируются – 1011

Означает ли это бинарный алгоритм поиска?

ответ

Смежные вопросы