В этой статье блога мы рассмотрим различные методы определения того, сортируется и вращается ли массив с использованием алгоритма двоичного поиска. Мы предоставим примеры кода для каждого метода, что позволит вам понять и реализовать эти методы в ваших собственных проектах. К концу этой статьи вы получите полное представление о том, как определить, эффективно ли сортируется и вращается массив.

Метод 1: линейный поиск
Самый простой подход — выполнить линейный поиск в массиве, чтобы проверить, отсортирован ли он и повернут ли он. Мы перебираем массив и сравниваем каждый элемент со следующим. Если мы находим порядок убывания, мы отмечаем этот индекс как точку вращения. Если мы не находим порядок убывания, массив не поворачивается.

Пример кода:

def is_sorted_rotated(arr):
    n = len(arr)
    for i in range(n):
        if arr[i] > arr[(i + 1) % n]:
            return i + 1
    return 0

Метод 2: двоичный поиск
Двоичный поиск можно использовать для определения эффективности сортировки и вращения массива. Мы модифицируем алгоритм бинарного поиска, чтобы найти точку вращения. Если средний элемент больше, чем следующий элемент, это означает, что следующий элемент является точкой вращения. Если средний элемент меньше предыдущего элемента, это означает, что средний элемент сам является точкой вращения. Мы повторяем этот процесс, пока не найдем точку вращения.

Пример кода:

def find_rotation_point(arr):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] > arr[mid + 1]:
            return mid + 1
        elif arr[mid] < arr[mid - 1]:
            return mid
        if arr[mid] > arr[high]:
            low = mid + 1
        else:
            high = mid - 1
    return 0

Метод 3: модифицированный бинарный поиск
Другой подход заключается в использовании двоичного поиска напрямую для поиска определенного целевого элемента. Мы определяем целевой элемент как наименьший элемент массива. Найдя индекс целевого элемента, мы можем определить точку вращения. Если целевой элемент находится с индексом 0, массив не поворачивается. В противном случае индекс целевого элемента дает нам точку вращения.

Пример кода:

def find_rotation_point_modified(arr):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] > arr[high]:
            low = mid + 1
        else:
            high = mid
    return low