Haikson

[ Everything is possible. Everything takes time. ]

Алгоритм линейного поиска на python

Здравствуйте, дорогие начинающие программисты. Сегодня я продолжу свой мини-экскурс по базовым алгоритмам программирования реализацией алгоритма линейного поиска на python. Ниже будут приведены 2 варианта решения задачи. Первый - классический, что в принципе и объяснит основу алгоритма, а второй - с исползованием хиростей python, которые, в принципе не являются большим секретом ;) Итак, классика: Основной принцип линейного поиска "зашифрован" в самом названии алгоритма. Задача - найти индекс элемента массива или None, если элемента нет в массиве. Алгоритм линейтного поиска является самым простым, очевидным, и, как следствие, медленным. Но в некоторых случаях, особенно при работе с заведомо маленькими массивами, он божет быть наиболее удобным. Для начала представим себе массив целочисленных значений. Чтобы найти элемент в массиве, необходимо перебрать все элементы данного списка и сверить значение с искомым. Но, обратите внимание, нет необходимости сверять все элемены списка с искомым значением.
def linear_search_simple(arr, search):
    for val in enumerate(arr):
        if val[1] == search:
            return val[0]
    return None

print linear_search_simple([1,2,3], 2)
Мы знаем, что enumerate возвращает итератор, каждый элемент которого - это tuple, первым элементом которого является индекс элемента в списке, а второй - значение. Поэтому в функции выше мы сверяем значение второго элемента с искомой и, если значения равны, то выходим из функции, вернув первое значение кортежа. Если перебор в цикле ничего не вернет, то возвращаем None. А вот и второй способ: Нам знаком метод list.index(val), где val - искомое значение. Этот метод возвращает индекс элемента в списке по искомому значению или ошибку, если элемента нет в списке. Так вот, чтобы ошибки не было, мы проверяем вхождение значения в список и только после этого выводим индекс элемента.
def linear_search(arr, search):
    return arr.index(search) if search in arr else None
На этом, собственно, все. Успехов на нелегком, но интересном пути в мир программирования.