Задача с собеседования в Яндекс.
Данная задача встречалась достаточно давно, но все же уметь ее решать будет полезно.
Вам дали массив a состоящая из различных чисел. Известно, что изначально массив был отсортирован по возрастанию, а потом сдвинуть налево на несколько шагов.
Например a = [5, 8, 10, 14, 20, 25, 0, 1, 2, 4]
Ваша задача найти минимальное число в массиве за O(logn)

Решение:
Ясно, что задача очень просто решается за O(n). Достаточно было бы пройтись по массиву и узнать минимальное число.
В задаче нам нужно найти этот элемент за log. Когда видим log мы думаем про деление на два. Но с другой стороны бинарный поиск как будто бы не должен работать, так как массив не является отсортированным.

Давайте скажем что type1 - это первый кусок массива, где все числа возрастали, а type2 - остальная часть. В нашем примере
type1 = [5, 8, 10, 14, 20, 25]
type2 = [0, 1, 2, 4]
По факту наша задача найти первый элемент в type2.

Давайте все таки попробуем написать бинарный поиск. Заранее обработаем особый случай a[0] < a[n - 1] в таком случае можно смело выводить a[0].
Давайте поставим границы бинарного поиска l = 0, r = n - 1, мы пока точно знаем, что a[l] > a[r].
Посмотрим на середину отрезка mid = (l + r) // 2, если a[l] < a[mid] это означает, что mid попал в type1 в таком случае мы можем смело сдвигать левую границу бинарного поиска.
Рассмотрим другой случай, когда a[l] > a[mid] - это означает, что mid попал в type2. Давайте в такие момента сдвигать r.
Вы можете заметить, что мы поддерживали инвариант a[l] >a[r] для всех l, r таких что r - l > 1.
В конце концов мы попадем в позицию минимума.

Важный вопрос, почему при a[l] > a[mid] мы сдвигали именно r, а не l ?
-Если бы сдвигали l у нас могла возникнуть ситуация a[l] < a[r] то есть l и r попали в type2 а этот случай плохой, так как l мог уйти за правую часть минимальной элемента, таким образом на подотрезке l, r не находился бы ответ, а такое в бинарном поиске допускать нельзя. Очень важно, чтобы на подотрезке l, r всегда находился ответ.

Время работы O(logn)