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

Question

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

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

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

Answer 1

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

Answer 2

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

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

Там еще одна очень важная вещь, чтобы иметь в виду:

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

Answer 3

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

Но если бы:

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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