a.py

# https://contest.yandex.ru/contest/23815/run-report/155574509/
#
# -- Принцип работы --
#
# Функция `broken_search()` выполняет поиск заданного значения в "сломанном" массиве целых чисел,
# элементы которого изначально были отсортированы по возрастанию, но затем, возможно, были сдвинуты
# на несколько позиций влево или вправо через границу массива по кольцу. Используемый алгоритм
# аналогичен стандартному бинарному поиску без рекурсии, но учитывает возможность того, что исследуемая
# часть массива, в которой мы пытаемся найти нужный элемент, может быть "сломана" (т.е., некорректно
# отсортирована).
#
# На каждом шаге алгоритма, если заданный элемент пока не найден, диапазон поиска уменьшается примерно
# в два раза. Чтобы учесть точку слома сортировки, для сужения диапазона поиска используется следующее
# правило:
#
# * Если искомое значение находится между левым и центральным элементом текущего диапазона поиска, то
#   продолжаем поиск в левой части интервала.
# * Если левая часть интервала отсортирована некорректно, но при этом искомое значение не находится
#   между центральным и правым элементом, то тоже пробуем продолжить поиск в левой части.
# * В остальных случаях, руководствуясь методом исключения, предполагаем, что нужный элемент находится
#   в правой части интервала.
#
# -- Доказательство корректности --
#
# Поскольку на каждом шаге алгоритма диапазон поиска экспоненциально сужается, то левая и правая границы
# диапазона рано или поздно сойдутся и искомый элемент будет найден, если он существует в массиве.
#
# -- Временная сложность --
#
# Вычислительная сложность алгоритма аналогична стандартному бинарному поиску. В лучшем случае (если
# целевое значение будет найдено на первой итерации поиска) временная сложность составляет `O(1)`. В
# среднем и худшем случаях временная сложность составляет `O(log n)`.
#
# -- Пространственная сложность --
#
# Поскольку для хранения дополнительных данных при поиске используется фиксированный набор вспомогательных
# локальных переменных, то пространственная сложность алгоритма составляет `O(1)`.

from __future__ import annotations

from collections.abc import Sequence


def broken_search(nums: Sequence[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        middle = (left + right) // 2

        if nums[middle] == target:
            return middle

        if (
                (nums[left] <= target < nums[middle]) or
                (nums[left] > nums[middle] and not nums[middle] < target <= nums[right])
        ):
            right = middle - 1
        else:
            left = middle + 1

    return -1


def test() -> None:
    arr = [19, 21, 100, 101, 1, 4, 5, 7, 12]
    assert broken_search(arr, 5) == 6


if __name__ == '__main__':
    test()