Допустим, нам дан отсортированный массив из n элементов и просят найти данный элемент в массиве.
Простой и понятный метод - использовать линейный поиск, который мы начинаем с первого элемента, сравниваем один за другим и находим нужный элемент. Чтобы продемонстрировать, скажем, у нас есть отсортированный массив из 10 различных чисел от маленького до большого, и мы хотим найти 70:
В худшем случае, чтобы найти его, мы должны пройти через весь массив, то есть когда элемент находится в последнем индексе. Если n увеличивается на m, количество сравнений / предположений, необходимых алгоритму, также увеличивается на m. Таким образом, мы можем скажем, линейный поиск имеет наихудшую временную сложность O (n) (подробнее об этом ниже).
А как насчет того, чтобы использовать бинарный поиск? А что такое бинарный поиск?
Из Википедии: Двоичный поиск сравнивает целевое значение со средним элементом массива; если они не равны, половина, в которой цель не может находиться, удаляется, и поиск продолжается на оставшейся половине, пока не будет найдено целевое значение. Если поиск заканчивается, а оставшаяся половина остается пустой, цель отсутствует в массиве ». Давайте нарисуем его, чтобы продемонстрировать:
Скажем, у нас есть тот же массив, и мы хотим найти 70:
На первом этапе мы находим среднюю точку и делим ее пополам, так что визуально мы имеем:
Ищем в первом тайме, 70 в них нет. Так что давайте проигнорируем это, и для второй половины мы найдем середину и снова разделим ее пополам. И поскольку у него нечетное количество элементов, давайте также включим медианное число (мы также не можем включать медианное число, это не будет иметь реального значения, поскольку тогда его будет включать другая половина), так что теперь у нас есть:
Для нашей новой первой половины, давайте поищем 70, в них все еще нет. Так что давайте снова проигнорируем это, найдем середину и разделим ее пополам на второй половине. Теперь у нас есть:
И на этот раз 70 человек в новом первом тайме. Мы завершили бинарный поиск.
Как мы видим, двоичный поиск намного эффективнее линейного поиска, поскольку каждый раз нам нужно перебирать только половину оставшегося массива. Фактически, двоичный поиск имеет только наихудшую сложность времени выполнения, равную O (log n) (log по соглашению - это база 2). И давайте сравним, насколько различаются производительность O (n) и O (log n) - скажем, у нас есть отсортированный массив из 1000000 элементов:
В худшем случае линейный поиск требует 1000000 попыток, чтобы найти целевой элемент.
В худшем случае для двоичного поиска требуется время выполнения log (1000000) = 19,93, примерно 20 предположений, чтобы найти целевой элемент.
Вот в чем разница!
Теперь вы можете спросить, почему у двоичного поиска сложность выполнения наихудшего случая равна O (log n)?
Напомним, согласно Википедии: в информатике нотация большого O используется для классификации алгоритмов в соответствии с тем, как их требования к времени работы или пространству растут по мере увеличения размера ввода. Он характеризует функции по темпам их роста.
Таким образом, для линейного поиска очевидно, что по мере роста размера массива сложность выполнения в наихудшем случае составляет O (n).
А как насчет двоичного поиска?
Для простоты предположим, что нам дан массив из 8 элементов, и тот, который нам нужно найти, «случайно» находится в последнем индексе (наихудший случай). Поэтому каждый раз мы делим наш массив пополам, пока у нас не останется только один элемент, а именно:
Если провести рефакторинг:
Для n элементов давайте проведем рефакторинг:
Давайте представим это в логарифмической форме, так как нам нужно k:
Вот почему в наихудшем случае сложность выполнения для двоичного поиска составляет O (log n). Самое удивительное в двоичном поиске то, что каждый раз, когда размер массива удваивается, количество предположений времени выполнения увеличивается только на 1!
А теперь подумайте, как мы обычно подходим к проблеме ...
По интуиции мы обычно пользуемся линейным поиском, не так ли? Но теперь мы знаем, что двоичный поиск может быть настолько эффективным, особенно для большой проблемы ...
Итак, как разработчику отлаживать?
В заключение хочу процитировать Дэна Абрамова:
Используйте бинарный поиск и научный метод. Не буквально в коде, а в том, как вы к нему подходите. Есть ошибка где-то между сайтами A и B? В середину положите бревно. Между точкой А и серединой? В середину положите еще одно бревно. Что-то не так с вводом? Устраните половину ввода. Работает? Попробуйте вторую половину. И т.д. Отладка может показаться очень произвольной, но она проста, когда вы делаете это механически. Наблюдайте, сформируйте гипотезу, придумайте способ ее проверить, повторите. И разрежьте вещи пополам, когда их слишком много.
