Здравствуйте, дорогие начинающие программисты.
Сегодня я продолжу свой мини-экскурс по базовым алгоритмам программирования реализацией алгоритма линейного поиска на 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
На этом, собственно, все. Успехов на нелегком, но интересном пути в мир программирования.