Линейный поиск или бинарный поиск или дерево бинарного поиска

Question

У меня есть небольшое сомнение здесь ...

Если я знаю, что элемент поиска в списке, скажем, содержащий 32 элемента, отсортированных по порядку, появляется в первых четырех позициях,

, который является лучшим алгоритмом поиска.

Для линейного поиска требуется как минимум 4 итерации .... Бинарный поиск не менее 5 итераций Как насчет бинарного дерева поиска ... это дает лучшее решение в этом случае или равно бинарному поиску ...

Я считаю, что линейный поиск будет лучше для таких обстоятельств ..

Кто-нибудь может подтвердить это, пожалуйста?

Answer 1

Если вы знаете, что местоположение находится в первых 4 позициях, лучше использовать линейный поиск, так как вам придется тестировать не более 4 элементов. При бинарном поиске lg 32 = 5 вам придется протестировать не более 5 элементов.

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

Вы также можете использовать HashTable или HashSet для O (1) времени, но опять же, для небольшого объема данных, линейный поиск, вероятно, будет быстрее, чем выполнение хэш-функции.

И если небольшая разница действительно имеет значение, я бы посоветовал измерять ее в среде, где она будет работать.

Answer 2

Если данные каким-то образом распределены равномерно, целесообразно использовать интерполяционный поиск.Используя знания о распределении, у вас есть хороший шанс угадать правильную позицию за один шаг.Ожидаемая сложность O (log (log (n))).

Вот ссылка на мои страницы, где у меня реализован алгоритм на Java: Algoritmy.net - реализация интерполяционного поиска

Answer 3

С таким количеством элементов и точным применением, которое у вас есть, дерево бинарного поиска будет излишним.

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

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

Answer 4

вы можете сделать бинарный поиск по первым 4 элементам.это будет LG 4 = 2 итерации!: -)