5 подписчиков
Как найти льва в пустыне?
Он сам тебя найдет, ну да ладно. Допустим лев шел по пустыне (прямая) с запада на восток и оставлял четкие следы. Мы летим не вертолете и хотим найти его как можно скорее. Мы можем посветить прожектором в точку и узнать проходил ли он там.
Можно конечно осветить все, но это явно будет долго и энергозатратно. Оптимально будет разделить пустыню напополам посмотреть есть ли следы в центре. Если есть то лев явно правее, иначе левее. Рекурсивно перейдем к меньшей задаче. Вуаля, лев найден.
Такой подход называется бинарным поиском. Если в первом алгоритме мы включим прожектор столько раз, сколько всего следов (n), то во втором подходе это уже log2(n). Что, согласись, сильно лучше.
Около минуты
19 декабря 2023