Волшебный индекс в массиве

Решение

Задача требует найти индекс, где значение элемента равно самому индексу в отсортированном массиве. Это классическая задача, которая демонстрирует применение бинарного поиска к нестандартной проблеме.

Оптимальное решение — Бинарный поиск

Поскольку массив отсортирован, мы можем использовать бинарный поиск вместо линейного сканирования. Это снизит сложность с O(n) до O(log n).

def find_magic_index(arr: list[int]) -> int:
    """
    Находит волшебный индекс, где A[i] = i в отсортированном массиве.
    
    Args:
        arr: Отсортированный массив
    
    Returns:
        Индекс, где A[i] = i, или -1 если такого нет
    
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_value = arr[mid]
        
        if mid_value == mid:
            return mid  # Нашли волшебный индекс
        elif mid_value < mid:
            # Если значение меньше индекса, идём вправо
            left = mid + 1
        else:
            # Если значение больше индекса, идём влево
            right = mid - 1
    
    return -1  # Волшебного индекса нет

Примеры использования

# Пример из условия
arr1 = [-1, 0, 2, 4, 6]
print(find_magic_index(arr1))  # 2

# Волшебный индекс в начале
arr2 = [0, 1, 2, 3]
print(find_magic_index(arr2))  # 0

# Волшебный индекс в конце
arr3 = [-5, -3, 0, 2, 4]
print(find_magic_index(arr3))  # 4

# Нет волшебного индекса
arr4 = [-2, -1, 5, 10]
print(find_magic_index(arr4))  # -1

# Единственный элемент
arr5 = [0]
print(find_magic_index(arr5))  # 0

Почему работает бинарный поиск?

Ключевое наблюдение: в отсортированном массиве каждый элемент отличается от предыдущего минимум на 1. Если A[mid] < mid, то все элементы слева от mid также будут меньше своих индексов (потому что они ещё меньше). Поэтому волшебный индекс может быть только справа.

Аналогично, если A[mid] > mid, волшебный индекс может быть только слева.

Решение с дополнительным условием

Если в массиве могут быть дубликаты, базовый бинарный поиск может не сработать:

def find_magic_index_with_duplicates(arr: list[int]) -> int:
    """
    Находит волшебный индекс в массиве с возможными дубликатами.
    
    Time Complexity: O(n) в худшем случае
    Space Complexity: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_value = arr[mid]
        
        if mid_value == mid:
            return mid
        
        # С дубликатами: когда A[mid] > mid, идём и влево, и вправо
        right_search = min(mid - 1, mid_value)
        left_search = max(mid + 1, mid_value)
        
        # Проверяем влево
        if right_search >= 0:
            right = right_search
        # Проверяем вправо
        elif left_search < len(arr):
            left = left_search
        else:
            break
    
    return -1

Сравнение подходов

Для собеседования QA Automation Engineer важно понимать, как бинарный поиск адаптируется к нестандартным задачам и почему это работает благодаря свойствам отсортированного массива.