Найти фиксированную точку только с одним входом (массивом) для функции

Question

Я пытаюсь найти фиксированную точку в массиве, используя функцию, которая принимает только один вход (массив).Проблема в том, что я пытаюсь избежать создания другой функции, которую эта функция может вызывать.Если бы я мог сделать это, эта ситуация была бы решена.Эти массивы будут содержать список отсортированных целых чисел для меня, чтобы перебрать.Я пытаюсь сохранить его время выполнения низким с помощью бинарного поиска.Я пробовал это 100 различными способами, и ничего не работает.

def fixed_point(a):    

    if len(a) <= 2: # tried len(a) == 0 and len(a) == 1
        return -1 

    mid = len(a)//2 # have used (len(a)-1)//2 as well

    if mid == a[mid]:
        return a[mid]

    if mid > a[mid]:
        return find_point(a[mid+1:])

    else:
        return find_point(a[:mid])

    return -1

Эта функция вернет -1, если не найдена фиксированная точка.

Эта функция также проходит 10000 тестовпостроен для этого, но по какой-то причине не может найти, что "5" является фиксированной точкой массива: [-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129]

Любопытно, что люди могут найти не так с этим кодом.

Answer 1

Чтобы повторить то, что я сказал в своем комментарии, проблема в том, что вы теряете след a.

Ваш подход рекурсивный, и вы передаете список с уменьшающимся размером при каждом вызове.Из-за этого середина, которую вы ищете, и середина, которую вы в конечном итоге сравниваете, не одинаковы.

Переключитесь на итеративный подход, и вы можете держать вещи в контексте оригинального a.

def fixed_point(a):
    l, u = 0, len(a)

    while l <= u:
        m = (l + u) // 2
        if m == a[m]:
            return m
        elif m > a[m]:
            l = m + 1
        else:
            u = m - 1

    return -1

>>> fixed_point([-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129])
5

Преимущество итерации также заключается в меньших накладных расходах памяти (нет необходимости в стеках вызовов), хотя на других языках некоторые компиляторы оптимизируют.

Answer 2

Основная проблема вашего алгоритма в том, что он написан, заключается в том, что вы теряете место в исходном массиве.Когда вы выполняете рекурсию, вы возвращаете фиксированную точку половины массива, но, например, в [-4, -2, 0, 2, 4], когда вы разбиваете массив и находите фиксированную точку в [2, 4], она не работает, потому что в * нет фиксированной точки.1003 *.Вам нужно передать смещение для каждого рекурсивного вызова, чтобы вы могли сказать что-то вроде if mid + offset == a[mid].