Приём, которым пользуются многие программисты
Ситуация: мы пишем приложение для магазина. Нам нужно предусмотреть такую ситуацию: приезжает машина с новыми продуктами на продажу, а приёмщик заносит все товары в список общего ассортимента магазина. Если такой товар уже есть в списке, то ничего не происходит, а если нет — он добавляется в общий список.
Теперь важное: ассортиментный список всегда отсортирован по алфавиту, поэтому новые товары должны добавляться так, чтобы не нарушать эту сортировку. Нам нужно придумать такой алгоритм, который:
проверит, есть ли такой товар в списке;
если есть — выведет сообщение;
если нет — найдёт для него нужное место и добавит товар в общий список.
Решение
То, что нам нужно сделать, называется бинарным поиском. Его суть в том, что есть упорядоченные данные и нужно найти место, куда добавить новое значение. Работает он так:
- Список делят пополам и смотрят на серединный элемент.
- Если он больше того, что нужно добавить, — берут вторую половину, если нет — работают с первой.
- С этой половиной делаем то же самое — делим пополам, смотрим на серединный элемент и выбираем новую половину.
- Так делаем до тех пор, пока половина не будет состоять из одного элемента, то есть начало половины совпадёт с его концом.
- Как только это произошло — смотрим на индекс этого элемента, из которого состоит половина, и ставим наши данные после него.
На этом принципе работает известный математический трюк, когда угадывают число от 1 до 100 за семь попыток:
Как угадать число от 0 до 100 за 7 попыток? ← тут теория;
Решаем кодом: программа угадает число за 7 попыток ←, а тут практика.
Теперь применим это к нашей ситуации. Сразу заведём переменные под список и новое значение:
Проверим, есть ли такие данные в списке. Если есть — выведем сообщение, и на этом всё:
Теперь поработаем со второй ситуацией, когда данных в списке нет. Так как Python умеет сравнивать строки между собой, мы легко сможем сравнить новое значение с любыми элементами списка. Используем это и напишем алгоритм бинарного поиска:
Мы помним, что нам нужно добавить новые данные после последней оставшейся половины. Граница этой половины хранится в переменной end, поэтому увеличиваем это значение на единицу и добавляем в список новый элемент:
Собираем код в одно целое, запускаем и смотрим результат:
['арбуз', 'вишня', 'дыня', 'киви', 'персик', 'яблоко']
Значит, мы всё сделали правильно и написали правильный алгоритм.