Зимняя школа в "Эврике"

Рассмотрим сначала задачу линейного поиска элемента в массиве. 
Необходимо реализовать функцию, которая проверяет, содержится ли в данном списке A данный элемент key. 
Функция будет возвращать значение True или False.
Это можно сделать при помощи цикла for с проверкой условия внутри цикла:

def search(A, key):
    for i in range(len(A)):
        if A[i] == key:
            return True
    return False

Возможна реализация, использующая цикл while без условия внутри: 

def search(A, key):
    i = 0
    while i < len(A) and A[i] != key:
        i += 1
    return i < len(A)

Также каждая из этих функций может возвращать индекс найденного элемента или специальное значение 
(например, −1), если элемент не найден:

def search(A, key):
    for i in range(len(A)):
        if A[i] == key:
            return i
    return -1

Возможна реализация, использующая цикл while:

def search(A, key):
    i = 0
    while i < len(A) and A[i] != key:
        i += 1
    if i < len(A):
        return i
    else:
        return -1

Поскольку все эти алгоритмы должны просмотреть весь список в поисках данного элемента, 
то сложность работы данных алгоритмов будет O(n) (где n — длина списка).