Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от
двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Данный алгоритм приведен здесь, для полноты изложения. Он мало где используется, только если в собственных проектах, которые не накладывают серьезных требований к производительности системы.
Рассматриваем, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е., в результате каждой проверки область поиска уменьшается на один элемент.
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
Вот и весь линейный поиск!)
Но есть более интересный метод -
двоичный поиск, милости просим к изучению.
