Как искать большой массив для объекта?

Question

Сегодня у меня было интервью, меня спросили, как искать число внутри массива, я ответил «двоичный поиск», он спросил меня, как насчет большого массива, в котором тысячи объектов (например, «Акции») ищут, например, по ценеакции, я снова сказал binarysearch, он сказал, что сортировка массива тысяч займет много времени, прежде чем применять binarysearch.

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

Answer 1

Мне задали аналогичный вопрос. Твист состоял в том, чтобы искать в отсортированном, а затем в несортированном массиве. Все мои ответы были неприемлемыми

1. Для отсортированного я предложил найти центр и сделатьлинейный поиск. Бинарный поиск также будет работать здесь
2. Для несортированных я снова предложил линейный.
3. Затем я предложил двоичный код, который является своего рода неправильным.
4. Предложил хранить массив вhashset и использовать хеширование.(Не принимается, поскольку высокий космический комплекс)
5. Я предложил Tree Set, представляющий собой красно-черное дерево, хорошо подходящее для поиска. (Не принято, поскольку высокий космический комплекс)
6. Также рассматривалось копирование в травление Arraylist.накладные расходы.

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

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

Любые комментарии приветствуются.

Answer 2

Я думаю, что интервьюер хочет, чтобы вы в другом случае проанализировали начальное состояние массива, какой алгоритм вы будете использовать. Конечно, вы должны знать, что вы можете построить хеш-таблицу, а затем O (1) может найти число, или, когда массив отсортирован (может быть, затрачено время на сортировку), вы можете использовать binarysearch или использовать некоторые другие структуры данных закончить работу.

Answer 3

Я не уверен, что он имел в виду.

Если вы просто хотите найти число один раз, и у вас нет никаких гарантий относительно того, отсортирован ли массив, тогда я не думаю, что вы сможете обойти линейный поиск. В среднем вам нужно будет искать в середине массива, прежде чем вы найдете значение, то есть ожидаемое время выполнения O (N); при сортировке вы должны касаться каждого отдельного значения, по крайней мере, один раз и, возможно, более того, то есть ожидаемое время выполнения O (N log N).

Но если вам нужно найти несколько значений, то время, потраченное на их сортировку, быстро окупается. С отсортированным массивом вы можете выполнить бинарный поиск за O (log N), поэтому наверняка по третьему поиску вы впереди, если вы потратили время на сортировку.

Вы можете добиться еще больших успехов, если вам разрешено создавать различные структуры данных для решения этой проблемы. Вы можете создать какой-то индекс, такой как хеш-таблица; но чемпионом структуры данных для такого рода проблем, вероятно, будет какая-то древовидная структура. Затем вы можете вставить новые значения в дерево быстрее, чем вы могли бы добавить новые значения и пересортировать массив, и поиск по-прежнему будет O (log N), чтобы найти любое значение. Доступны различные виды деревьев: двоичное дерево, B-дерево, Trie и т. Д.

Но, как сказал @Hot Licks, для такого рода вещей часто используется хеш-таблица, и ее довольно дешево обновлять: вы просто добавляете значение в основной массив и обновляете хеш-таблицу, чтобы указать новое значение , И хеш-таблица очень близка к O (1) времени, которое вы не можете превзойти. (Хеш-таблица равна O (1), если нет хеш-коллизий; при условии хорошего хеш-алгоритма и достаточно большой хеш-таблицы коллизий почти не будет. O (N) где N - среднее число коллизий хешей на «корзину». Если я ошибаюсь, я ожидаю, что это будет исправлено очень быстро, это StackOverflow!)