Бинарный поиск
Итак, я хочу понять больше о бинарном поиске, потому что я не очень понимаю. Бинарный поиск требует предварительного условия, что массив отсортирован. Я правильно понял? Похоже, что метод должен проверить это предварительное условие и выдать исключение, если оно не выполнено. Но почему проверка предварительных условий плохая идея?
6 ответов
Это плохая идея, потому что проверка отсортированных данных занимает n
шаги. Весь поиск о log(n)
шаги.
Если вы собираетесь проверить, вы можете также выполнить линейный поиск.
Смысл бинарного поиска в том, что, поскольку данные уже отсортированы, вы можете быстро найти нужную информацию.
Возьми телефонную книгу, которая отсортирована по фамилии.
Как вы находите кого-то в телефонной книге? Вы открываете его на странице, которая, по вашему мнению, будет близка к тому, что вы хотите, а затем начинаете перелистывать страницы.
Но вы не переворачиваете одну страницу каждый раз, если вы много пропустили, вы переворачиваете кучу страниц, а затем, наконец, начинаете переворачивать по одной, пока, наконец, не начнете просматривать одну страницу.
Это то, что делает бинарный поиск. Поскольку данные отсортированы, он знает, что может многое пропустить и еще раз взглянуть, и сосредоточится на информации, которую вы хотите.
Бинарный поиск делает 1 сравнение для каждого удвоенного числа элементов. Таким образом, для сбора 1024 элементов потребуется максимум 10 сравнений, чтобы найти вашу информацию или, по крайней мере, выяснить, что ее там нет.
Если вы перед запуском фактического бинарного поиска выполнили полный прогон, чтобы проверить, отсортированы ли данные, вы можете просто выполнить сканирование информации. Полный прогон + бинарный поиск потребует N + log2 N операций, поэтому для 1024 элементов потребуется около 1034 сравнений, тогда как для простого сканирования информации в среднем потребуется половина, что составляет 512.
Поэтому, если вы не можете гарантировать, что данные отсортированы, вы не должны использовать бинарный поиск, так как он будет лучше, чем простое сканирование.
Изменить: я скажу это, хотя, вы могли бы добавить шаг кода только для отладки, чтобы проверить это, чтобы поймать ошибки в коде, который должен подготовить данные для бинарного поиска, но знаю, что из-за того, что я написал выше это увеличит общее время выполнения, поэтому в зависимости от того, что вы хотите сделать с этой проверкой, вы можете добавить или не добавить ее. Но он не должен присутствовать в коде релиза.
Да, бинарный поиск включает в себя 0(log n) шагов, а проверка всей отсортированной последовательности включает 0(n) шагов. С моей точки зрения, это хорошо проверить в режиме отладки, а не во время RELEASE.
Бинарный поиск предполагает, что входные данные отсортированы. Так что здесь вы правы.
Теперь вообще проверяю, отсортированы ли данные какое-то время. Поэтому выполнение этого перед каждым поиском сделает поиск действительно неэффективным.
Подробнее
Предположим, что "n" - это количество ваших данных.
Бинарный поиск O(log(n))
операция в худшем случае, чтобы найти элемент. Чтобы убедиться, что данные отсортированы, требуется O(n)
операции.
Так что, если мы будем проверять предварительные условия каждый раз для очень больших n
мы начнем тратить большую часть времени на проверку предварительных условий, чем на фактический поиск.
И не так сложно сказать, когда вы увидите такой эффект. Я только подсчитал, сколько времени вы потратите на предварительную проверку по сравнению с фактическим поиском
- Для 1 элемента вы не тратите время на поиск.
- Для 2 элементов вы тратите 50% на поиск.
- Для 5 элементов вы тратите 46% на поиск
- Для 20 элементов вы тратите 22% на поиск.
- На 100 элементов вы тратите 7% на поиск.
И так далее. В каждом случае отдых вовремя тратится на проверку предварительных условий.
Исходный вопрос предполагает, что вы используете бинарный поиск по коллекции данных. Это не всегда так. Много раз вы просто пытаетесь вычислить число в некотором интервале.
Предположим, вы пытаетесь рассчитать оптимальную настройку скорости вращения вентилятора. По какой-то причине вы не можете найти выражение закрытой формы, поэтому вы моделируете поток воздуха при различных настройках скорости.
Предполагая, что вентилятор может работать на любой скорости от 0 до 5000 об / мин, вам на самом деле не нужно создавать список возможных скоростей. Вы просто находите среднее значение предыдущего минимума и максимума на каждом шаге двоичного поиска.
В дополнение к тому, что все остальные говорили о времени выполнения (O(n), чтобы проверить все элементы, и O(log(n)), чтобы запустить бинарный поиск.)
Я думаю, что вы неправильно понимаете идею предварительного условия. Предварительные условия и постусловия являются контрактом. Если ваше предварительное условие истинно, и вы запускаете свой алгоритм, тогда ваше условие публикации будет верным. Если ваше предварительное условие является ложным, то вы не даете никаких гарантий на почтовое условие.
Таким образом, в основном бинарный поиск говорит следующее: если данные, которые вы мне даете, уже отсортированы, то я могу сообщить вам положение определенного фрагмента данных или, если его нет, выполнить примерно log (n) проверки. Если данные не отсортированы, я не даю никаких гарантий относительно своего ответа.
Работа, которая переносит вас из вашего предусловия в ваше постусловие, если ваш алгоритм. В этом случае бинарный поиск.