Написать алгоритм, который определяет, принадлежит ли заданное число к отсортированному списку чисел, со сложностью 𝑜(𝑛).?

Сложность O(n), как и заметили, здесь действительно излишняя. В отсортированном массиве можно добиться алгоритмической сложности O(log n). И такая сложность легко достигается алгоритмом бинарного поиска.

Смысл алгоритма:

— пусть нам нужно найти в списке элемент k

— возьмём список и найдём элемент ровно посередине. Посмотрим, больше ли этот элемент k. Если да, то k, очевидно, нам нужно искать слева от этого элемента (в левой половине списка), а если нет — то в правой. Ну это если список отсортирован по возрастанию, в противном случае ровно наоборот.

А в половине списка ищем элемент таким же образом! Делим его пополам, смотрим средний элемент, сравниваем с k и выбираем нужную половину этой половины списка. И так далее, пока мы не дойдём до списка из одного элемента. Если этот элемент равен k, то мы нашли нужный элемент, а если нет — числа k в массиве вообще нет.

Реализуется обычно с помощью введения границ l и r — в каких пределах мы работаем сейчас, то есть, полуинтервал [l; r). Ищем, пока границы не сомкнутся (то есть, когда l станет равно r - 1).

a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
k = 55

n = len(a)

l = 0
r = n

while l != r - 1:
    m = (l + r) // 2  # ищем средний элемент

    if a[m] >= k:  # сравниваем средний элемент с k
        r = m  # смещаем правую границу к m. Таким образом, теперь мы ищем ответ на полуинтервале [l; m)
    else:
        l = m  # иначе ищем на [m; r)

if a[l] == k:  # если нашли элемент
    print(l)
else:
    print("Нет такого элемента :—(")

Ну давайте теперь оценим сложность такого алгоритма.

Очевидно, каждый раз мы делим исходный массив пополам. Значит, алгоритм пройдёт log2(n) итераций. Отсюда алгоритмическая сложность — O(log n).