Ситуация: мы пишем приложение для магазина. Нам нужно предусмотреть такую ситуацию: приезжает машина с новыми продуктами на продажу, а приёмщик заносит все товары в список общего ассортимента магазина. Если такой товар уже есть в списке, то ничего не происходит, а если нет — он добавляется в общий список.
Теперь важное: ассортиментный список всегда отсортирован по алфавиту, поэтому новые товары должны добавляться так, чтобы не нарушать эту сортировку. Нам нужно придумать такой алгоритм, который:
- проверит, есть ли такой товар в списке;
- если есть — выведет сообщение;
- если нет — найдёт для него нужное место и добавит товар в общий список.
То, что нам нужно сделать, называется бинарным поиском. Его суть в том, что есть упорядоченные данные и нужно найти место, куда добавить новое значение. Работает он так:
- Список делят пополам и смотрят на серединный элемент.
- Если он больше того, что нужно добавить, — берут вторую половину, если нет — работают с первой.
- С этой половиной делаем то же самое — делим пополам, смотрим на серединный элемент и выбираем новую половину.
- Так делаем до тех пор, пока половина не будет состоять из одного элемента, то есть начало половины совпадёт с его концом.
- Как только это произошло — смотрим на индекс этого элемента, из которого состоит половина, и ставим наши данные после него.
На этом принципе работает известный математический трюк, когда угадывают число от 1 до 100 за семь попыток:
Как угадать число от 0 до 100 за 7 попыток? ← тут теория;
Решаем кодом: программа угадает число за 7 попыток ← а тут практика.
Теперь применим это к нашей ситуации. Сразу заведём переменные под список и новое значение:
# исходный список
list = ['арбуз','вишня','дыня','персик','яблоко',]
# новые данные, которые нужно добавить
target = 'киви'Проверим, есть ли такие данные в списке. Если есть — выведем сообщение, и на этом всё:
# если это уже есть в списке
if target in list:
# выводим сообщение
print('Такое значение уже есть в списке')
# останавливаем программу
exit()Теперь поработаем со второй ситуацией, когда данных в списке нет. Так как Python умеет сравнивать строки между собой, мы легко сможем сравнить новое значение с любыми элементами списка. Используем это и напишем алгоритм бинарного поиска:
# если таких данных в списке нет
else:
# начальная граница
start = 0
# конечная граница
end = len(list)-1
# пока начальная граница меньше конечной
while start <= end:
# находим индекс серединного элемента
mid = (start + end)//2
# если значение этого элемента больше нашего
if list[mid] > target:
# сдвигаем конечную границу к середине
end = mid - 1
# в противном случае
else:
# сдвигаем начальную границу к середине
start = mid + 1
# повторяем так до тех пор, пока границы не сойдутсяМы помним, что нам нужно добавить новые данные после последней оставшейся половины. Граница этой половины хранится в переменной end, поэтому увеличиваем это значение на единицу и добавляем в список новый элемент:
Собираем код в одно целое, запускаем и смотрим результат:
['арбуз', 'вишня', 'дыня', 'киви', 'персик', 'яблоко']
Значит, мы всё сделали правильно и написали правильный алгоритм.
# исходный список
list = ['арбуз','вишня','дыня','персик','яблоко',]
# новые данные, которые нужно добавить
target = 'киви'
# если это уже есть в списке
if target in list:
# выводим сообщение
print('Такое значение уже есть в списке')
# останавливаем программу
exit()
# если таких данных в списке нет
else:
# начальная граница
start = 0
# конечная граница
end = len(list)-1
# пока начальная граница меньше конечной
while start <= end:
# находим индекс серединного элемента
mid = (start + end)//2
# если значение этого элемента больше нашего
if list[mid] > target:
# сдвигаем конечную границу к середине
end = mid - 1
# в противном случае
else:
# сдвигаем начальную границу к середине
start = mid + 1
# повторяем так до тех пор, пока границы не сойдутся
# добавляем наше значение на нужную позицию
list.insert(end+1, target)
# выводим обновлённый список
print(list)
