На этом шаге мы рассмотрим особенности реализации такого поиска.

    Сначала допустим, что список не (обязательно) сортирован. Любой алгоритм потребовал бы в худшем случае, когда элемент вообще не принадлежит списку, n сравнений. Отметим, что любой метод должен проверить каждый элемент списка, чтобы удостовериться, что его нет в списке. В этом случае алгоритм осуществляет "линейный поиск" элемента (последовательный перебор) в списке, время выполнения которого Ο(n).

    Ясно, что размер задачи - n. Если список пуст, метод может просто вернуть -1. Другое начальное условие может вернуть позицию элемента, если он найден. Это начальное условие будет зависеть от способа декомпозиции. Если уменьшать размер задачи на 1, отбрасывая последний элемент списка, то начальное условие должно проверить, находится ли x в последней позиции. Если действительно a_n-1 = x, то метод может просто вернуть n - 1. Иначе будет выполняться рекурсивный вызов для решения подзадачи размера n - 1, а её результатом будет именно окончательный результат подзадачи, которая приводит к хвостовому рекурсивному решению. В примере 5.5 приводится возможная реализация описанной функции линейного поиска.

def linear_search_tail(a, x):
    n = len(a)
    if a == []:
        return -1
    elif a[n - 1] == x:
        return n - 1
    else:
        return linear_search_tail(a[:n - 1], x)    

    В заключение стоит отметить, что в предыдущей декомпозиции позиции элементов подсписка совпадают с позициями исходного списка. Но если бы декомпозиция отбрасывала первый элемент списка, то все индексы в подсписке были бы на 1 меньше, чем в исходном. Например, если список - [2, 8, 5], то в первом случае элемент 8 в подсписке [2, 8] тоже был бы в позиции 1, а во втором он находился бы в позиции 0 в подсписке [8, 5]. Это приводит к более сложным методам, которые требуют дополнительного параметра. Например, в примере 5.6 приведено решение, добавляющее 1 к результату каждого рекурсивного вызова. В тривиальном случае, когда x = a₀, метод возвращает 0, но для пустого списка начальное условие сложнее. Отметим, что по достижении этого начального условия алгоритм уже добавил n единиц в предыдущих n рекурсивных вызовах. Таким образом, он должен вернуть n - 1, где n - длина исходного списка (но не длину входного параметра, так как в этот момент он равен 0), чтобы в итоге вернуть -1, поскольку x не найден. Так как n не может быть получен из пустого списка, его нужно передавать дополнительным параметром каждому вызову функции, чтобы восстановить в начальном условии. По этой причине код требует охватывающего метода, когда третьим параметром рекурсивной функции является n.

def linear_search_linear(a, x, n):
    if a == []:
        return -n - 1
    elif a[0] == x:
        return 0
    else:
        return 1 + linear_search_linear(a[1:], x, n)    


def linear_search_linear_wrapper(a, x):
    return linear_search_linear(a, x, len(a))

    В последней декомпозиции алгоритм начинает поиск элемента с индекса 0, постепенно достигая индекса n - 1. Другое решение заключается в явном указании индекса элемента, который будет каждый раз сравниваться с x в рекурсивном вызове. Для этого вводится новый параметр-сумматор, который увеличивается при каждом вызове функции и приводит к хвостовой рекурсии в примере 5.7, возвращающей правильное значение -1 для пустого списка. Функция должна вызываться с параметром-сумматором индекса, равным 0, из охватывающего метода-оболочки. Наконец, обратите внимание, что результат хранится именно в этом параметре.

def linear_search_tail_alt(a, x, index):
    if a == []:
        return -1
    elif a[0] == x:
        return index
    else:
        return linear_search_tail_alt(a[1:], x, index + 1)    


def linear_search_alt_tail_wrapper(a, x):
    return linear_search_tail_alt(a, x, 0)

    На следующем шаге мы рассмотрим двоичный поиск в сортированном списке.

Предыдущий шаг Содержание Следующий шаг