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

Question

Скажем,

У меня есть 1000 элементов в массиве, и я хочу найти 10 элементов в этом массиве, и какой поисковый механизм наиболее подходит?

Кроме того, если в случае, мне нужно найти 900 элементов из того же массива, то какой метод поиска хорош?

Линейный или двоичный поиск?

Заранее спасибо.

Answer 1

Если элементы не отсортированы, вы не можете выполнить двоичный поиск. Но бинарный поиск намного быстрее, чем линейный поиск (вам нужно посмотреть в среднем на 10 элементов, а не на 500), что лучше всего сортировать свой список (используя такой алгоритм, как quicksort), а затем выполнять двоичный поиск ,