Бинарный поиск

Question

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

Answer 1

Это плохая идея, потому что проверка данных отсортируется n шаги Весь поиск о log(n) шаги
Если вы собираетесь проверить, вы также можете выполнить линейный поиск.

Answer 2

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

Возьмите телефонную книгу, которая отсортирована по фамилии.

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

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

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

Бинарный поиск проводит 1 сравнение для каждого удвоенного числа предметов. Таким образом, для коллекции элементов 1024 потребуется около 10 сравнений, что самое большее, чтобы найти вашу информацию или, по крайней мере, выяснить, что ее там нет.

Если вы, прежде чем запустить фактический бинарный поиск, выполняет полный проход, чтобы проверить, отсортированы ли данные, вы можете просто сделать сканирование для информации. Полный пробег + двоичный поиск потребует операций N + Log2 N, поэтому для 1024 элементов для этого потребуется около 1034 сравнения, тогда как для простого сканирования информации в среднем потребуется половина, что составляет 512.

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

---

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

Answer 3

Да, двоичный поиск включает в себя 0 (log n) шагов, а проверка всей последовательности сортируется, включает в себя 0 (n) шагов. С моей точки зрения хорошо проверить его в режиме отладки, а не во время выпуска.

Answer 4

Бинарный поиск Предполагается, что входные данные отсортированы. Итак, вы правы.

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

Более подробная информация.

Предположим, что 'n' - это объем ваших данных.

Бинарный поиск потребности O(log(n)) Операция в худшем случае, чтобы найти элемент. Убедиться, что данные отсортированы O(n) операции.

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

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

• Для 1 элемента вы не тратите время на поиск.
• Для 2 элементов вы тратите 50% на поиск.
• На 5 элементов вы тратите 46% на поиск
• Для 20 элементов вы тратите 22% на поиск.
• На 100 элементов вы тратите 7% на поиск.

И так далее. В каждом случае отдых вовремя тратит на проверку предварительной кондиционирования.

Answer 5

В дополнение к тому, что все остальные сказали о времени выполнения (O (n), чтобы проверить все элементы, против O (log (n)) для выполнения бинарного поиска.)

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

Таким образом, в основном бинарный поиск говорит: если данные, которые вы мне даете, уже отсортированы, то я могу сказать вам положение определенного фрагмента данных, или если они не присутствуют, выполняя приблизительно проверки log (n). Если данные не отсортированы, я не даю никаких гарантий о своем ответе.

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

Answer 6

Первоначальный вопрос предполагает, что вы используете бинарный поиск по сбору данных. Это не всегда так. Много раз вы просто пытаетесь вычислить число в некотором интервале.

Предположим, вы пытаетесь рассчитать оптимальную настройку скорости для вентилятора. По какой -то причине вы не можете найти выражение закрытой формы, поэтому вы имитируете поток воздуха в разных настройках скорости.

Предполагая, что вентилятор может работать на любой скорости от 0 млн / мин до 5000 об / мин, вам на самом деле не нужно генерировать список возможных скоростей. Вы просто находите среднее значение предыдущего минимума и максимума на каждом этапе бинарного поиска.