Примеры использования бинарного поиска

Question

Я только что понял, что за мои 4 с лишним года программирования на Java (в основном, для настольных приложений) я никогда не использовал методы двоичного поиска в классе Arrays для чего-либо практического.Даже не один раз.Вот некоторые причины, по которым я могу придумать:

1. 100% времени, когда вы можете избавиться от линейного поиска, карт или чего-то еще, кроме двоичного поиска.
2. почти никогда не сортируется, и для его сортировки требуется дополнительный шаг сортировки.

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

Answer 1

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

Answer 2

Я бы сказал, что это сводится к следующему:

Если мы собираемся выполнить бинарный поиск, у нас будет ключ для поиска. Если у нас есть ключ, мы, вероятно, используем карту вместо массива.

Есть еще одна очень важная вещь, которую нужно иметь в виду:

Двоичный поиск является ярким примером того, как мышление, как хороший программист, сильно отличается от мышления, как нормальный человек . Это один из тех когнитивных скачков, который заставляет вас задуматься о том, чтобы делать операции, которые традиционно выполняются (когда выполняются людьми), во время порядка n и сводить его к времени порядка lg-n. И это делает его очень, очень полезным, даже если он никогда не используется в рабочем коде.

Answer 3

Для производственного кода на моей повседневной работе до сих пор всегда достаточно Set или Map.

Для алгоритмических задач, которые я решаю для развлечения, бинарный поиск - очень полезный метод.Для начала, если набор элементов никогда не изменяется (т.е. вы никогда не собираетесь вставлять или удалять элементы в запрашиваемом наборе), то Map / Set не имеет преимущества над бинарным поиском - и бинарный поиск над простым массивомизбегает больших накладных расходов, связанных с запросом более сложной структуры данных.Во многих случаях я видел, что это на самом деле быстрее, чем HashMap.

. Двоичный поиск также является более общей техникой, чем просто запрос на членство в наборе.Бинарный поиск может быть выполнен по любой монотонной функции, чтобы найти значение, для которого функция удовлетворяет определенным критериям.Вы можете найти более подробное объяснение здесь .Но, как я уже сказал, моя работа не вызывает достаточно вычислительных проблем, чтобы это было применимо.

Answer 4

Я почти никогда не использую бинарный поиск.

Но я бы, если:

• Мне нужно было искать один и тот же список несколько раз
• список был достаточно длинным, чтобы иметь проблемы с производительностью (хотя я часто виновен в микро-оптимизации)

Однако я часто использую хэш-таблицы / словари для быстрого поиска.

Answer 5

Предположим, вам нужно искать элемент в списке.

Вы можете использовать линейный поиск, вы получите O (n) .

В качестве альтернативы выможет отсортировать его по быстрому алгоритму (O (log n) * n) и двоичному поиску (O (log n)).Вы получите O ((log n) * n + log n) .

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