Линейный поиск

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

Данный алгоритм приведен здесь, для полноты изложения. Он мало где используется, только если в собственных проектах, которые не накладывают серьезных требований к производительности системы.

Рассматриваем, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е., в результате каждой проверки область поиска уменьшается на один элемент.

def linearSearch(li, x):
    i = 0
    length = len(li)
    while i<length and x<> li[i]:
        i+=1
    return i if i<length else None

Никлаус Вирт описал модернизацию метода, при которой мы избавляемся от одного сравнения на каждом витке цикла. А именно от проверки окончания строки. Для этого мы добавляем искомый элемент в самый конец, что гарантирует нам остановку по одному условию, а финальная проверка на позицию найденного элемента, покажет подставной он или нет)

def linearSearchVirt(li, x):
    i = 0
    length = len(li)-1
    while x x<> li[i]:
        i+=1
    return i if i<length else None

Вот и весь линейный поиск!)
Но есть более интересный метод -  двоичный поиск, милости просим к изучению.