Бинарный поиск или почему перебор - это не лучшее решение

Всем привет, сегодня поговорим про очень эффективный и простой в освоении начинающими алгоритм - бинарный поиск.

Введение

Начнем пожалуй с примера. Вы и ваш друг играете в такую игру. Ваш друг загадывает число от 1 до 100 и ваша задача угадать число, которое он загадал. В правилах есть небольшие нюансы: если вы называете число, но оно больше загаданного, то ваш ваш друг говорит "перебор"; а если меньше, то говорит "недобор". Разберем две стратегии.

1) Просто называем все числа подряд.

2) Применим алгоритм бинарного поиска.

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

А вот второй алгоритм уже интереснее. Что мешает нам просто взять и назвать число посередине? Правильно, ничего. Поэтому первым ходом мы говорим 50, и представим, что наш друг сказал Перебор. Значит мы одним ходом убрали сразу 50 чисел.

Теперь у нас остался диапазон от 1 до 49, давайте назовем число 25. Наш друг говорит Недобор.

Ну и следующим ходом говорим 37 и отгадываем. Да, друг мог загадать например 36, но мы бы просто продолжили поиск по нашему алгоритму и рано или поздно дошли бы до числа. А как вы думаете, какое максимальное количество попыток вы сделаете благодаря этому алгоритму? Ответ: 7. ДА, благодаря этому алгоритму вы не сделаете больше 7 шагов в любом случае. Теперь вы понимаете почему это лучше, чем простой перебор. В первом случае при наихудших обстоятельствах ваши попытки могут дойти до 100. А вот во втором случае у вас уйдет не больше 7 попыток. Это ж вообще кайф.

Сложность алгоритма

У вас наверное возник вопрос: а как ты расчитал максимальное количество попыток? Весь секрет в сложности этого алгоритма.

Сейчас я не буду давать определений тому, что такое Big О и что такое сложность алгоритмов - об этом вы сможете почитать в интернете или чуть позже напишу об этом пост. Мы тут все-таки говорим про бинарный поиск.

Первый алгоритм является линейным, то есть O(n) и тут количество попыток или итераций зависит от числа n. Грубо говоря, конкретно в этой игре у нас есть последовательность чисел от 1 до n. Поэтому количество попыток = числу n.

Второй алгоритм можно выразить как O(log n). Основанием логарифма является число 2. Тут мы также, вместо n подставляем количество чисел, то есть 100. и считаем. log 100 ~ 6.64385618, но т.к. количество попыток это натуральное число, то мы округляем до 7.

Определение и принцип работы

Бинарный поиск — тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент. Другие его названия — двоичный поиск, метод половинного деления, дихотомия.

Основная последовательность действий алгоритма выглядит так:

1. Сортируем массив данных.
2. Делим его пополам и находим середину.
3. Сравниваем срединный элемент с заданным искомым элементом.
4. Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим ее пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3.

Примечание

Алгоритм бинарного поиска имеет смысл только тогда, когда ваш список отсортирован, иначе он просто не будет работать корректно.

Реализация алгоритма

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

Сначала создадим функцию и определим несколько переменных.

def binary_search(array: list[int], item: int) -> [int, str]:    
    low = 0  # начало списка    
    high = len(array) - 1  # конец списка    
    mid = len(array) // 2  # середина списка

На вход мы принимаем два значения: список с числами и число, которое мы ищем. Обратно функция отдает индекс числа, которое мы ищем или строку, в случае, если такого числа нет в списке.

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

while array[mid] != item and low <= high:    
    if item > array[mid]:        
        low = mid + 1    
    else:        
        high = mid - 1    
    mid = (low + high) // 2

Ну и в конце проверяем, если число в начале больше, чем в конце, то такого заданного числа просто нет в списке, иначе отдаем индекс этого числа.

if low > high:    
    return 'Нет такова'
else:    
    return mid

В итоге, все вместе это будет выглядеть вот так:

def binary_search(array: list[int], item: int) -> [int, str]:    
    low = 0  # начало списка    
    high = len(array) - 1  # конец списка    
    mid = len(array) // 2  # середина списка    
    while array[mid] != item and low <= high:        
        if item > array[mid]:            
            low = mid + 1        
        else:            
            high = mid - 1        
        mid = (low + high) // 2    
    if low > high:
        return 'Нет такова'
    else:
        return mid
        
my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))  # 1
print(binary_search(my_list, 2))  # Нет такова

Заключение

В заключении хотелось бы сказать, что применение такого алгоритма сильно упростит вашу жизнь в задачах подобно типа. Сложность этого алгоритма считается одной из самых быстрых и это несомненно плюс. На одном только leetcode - 261 задача в которых требуется применение алгоритма бинарного поиска.

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

• Телеграм

Подписываемся сюда:

• Телеграм-канал
• Инста

Проектики тут:

• Github

Всем спасибо, всем пока🥰