Когда данные хранятся в списке, вам часто придется выполнять поиск по списку, чтобы увидеть, хранится ли там конкретное значение. В этой статье рассматривается шаблон для решения этой задачи — шаблон Поиск в списке. В конце статьи я покажу вам, как использовать встроенную функцию Python для выполнения этой задачи без написания собственной функции.
Шаблон списка поиска
Шаблон Поиск в списке реализует последовательный или линейный поиск в списке. Это означает, что поиск начинается с первого элемента списка и заканчивается, когда либо найден искомый элемент, либо поиск достигает конца списка.
Я собираюсь реализовать этот шаблон с помощью функции. Одна версия шаблона вернет истинное значение в случае успешного поиска и ложное значение в случае неудачного поиска. Во втором варианте функция будет возвращать позицию найденного значения, если поиск будет успешным, и функция вернет -1, если поиск не увенчался успехом. Причина, по которой неудачный поиск возвращает -1, заключается в том, что это недопустимая позиция в списке.
Вот псевдокод для шаблона Поиск в списке с использованием цикла while, который возвращает True или False:
Найдено = false
начальная переменная позиции списка равна 0
пока искомое значение не найдено:
если достигнут конец списка:
указать поиск сбой
если элемент найден:
указать успех поиска
увеличить переменную положения списка на 1
Вы также можете реализовать этот шаблон с помощью цикла for, и я оставлю это в качестве упражнения для читателя.
Вот псевдокод для версии, которая возвращает позицию списка или -1, на этот раз с использованием цикла for:
для каждого элемента списка:
если элемент найден:
установить foundPos в позицию элемента
прервать цикл
вернуть foundPos
Преждевременный выход из цикла является спорным вопросом, но я верю в эффективность, а не в программную инженерию, поэтому я включил разрыв в псевдокод.
Реализация шаблона поиска в списке — возврат True или False
Теперь давайте рассмотрим реализацию первого из двух представленных выше примеров псевдокода. Этот шаблон лучше всего реализовать с помощью функции, в которую мы передаем список, который мы хотим найти, и значение, которое мы ищем, в качестве аргументов. Функция возвращает истинное значение, если значение найдено в списке, и возвращает ложное значение в противном случае.
Первая реализация предназначена для версии цикла while, которая возвращает логическое значение. Вот определение функции:
def find(list, value):
found = False
listPos = 0
while not found:
if listPos == len(list):
return found
elif list[listPos] == value:
found = True
return found
else:
listPos = listPos+1
Давайте проверим эту функцию, используя ее для поиска в списке случайно сгенерированных чисел. Вот программа:
from random import randint
grades = []
numGrades = 20
for i in range(0, numGrades):
grades.append(randint(1,101))
print(grades)
searchVal = int(input("Enter a value to search for: "))
if (find(grades, searchVal)):
print(searchVal,"is in grades.")
else:
print(searchVal,"is not in grades.")
Вот результат двух запусков программы:
[83, 73, 81, 97, 56, 13, 53, 46, 77, 90, 40, 81, 5, 65, 5, 56, 6, 82, 45, 31] Enter a value to search for: 77 77 is in grades. [91, 12, 32, 56, 64, 35, 96, 30, 17, 82, 97, 96, 82, 47, 98, 83, 50, 101, 48, 71] Enter a value to search for: 55 55 is not in grades.
Теперь давайте напишем версию функции find с циклом for:
def find1(list, value):
for i in range(0, len(list)):
if list[i] == value:
return True
return False
Обратите внимание, что на этот раз я не использовал логическую переменную, а просто возвращал True, если искомое значение было найдено в списке. Если поиск не удался, функция автоматически возвращает False, так как этот оператор возврата является последней строкой функции.
Некоторые люди считают этот стиль программирования плохим, поскольку в функции есть два оператора возврата. Другие люди просто считают это более эффективным способом написания функции. Вы должны понимать, что как только функция достигает оператора return, никакие другие операторы в функции выполняться не будут. Я не буду судить о том, какая версия лучше, так как оба способа выполняют свою работу, но просто возврат значения true или false определенно более эффективен и приводит к меньшему количеству кода, но столь же легкому для понимания коду.
Реализация шаблона поиска в списке — возврат позиции или -1
Теперь давайте посмотрим, как реализовать шаблон Поиск в списке, который возвращает либо позицию в списке, где найдено значение, либо -1, если значение отсутствует в списке. Я реализую функцию, используя цикл while loop и цикл for.
Вот версия while loop функции find :
def find(list, value):
pos = 0
while pos < len(list):
if list[pos] == value:
return pos
pos = pos + 1
return -1
Функция возвращает позицию в списке, где находится искомое значение, или функция возвращает -1.
Вот программа для проверки функции:
grades = []
numGrades = 20
for i in range(0, numGrades):
grades.append(randint(1,101))
print(grades)
searchVal = int(input("Enter a value to search for: "))
position = find(grades, searchVal)
if (position > -1):
print("Found",searchVal,"at position",position)
else:
print(searchVal,"is not in the list.")
Вот результат двух запусков программы:
[92, 37, 64, 59, 48, 61, 56, 8, 59, 10, 20, 29, 75, 39, 49, 30, 75, 62, 12, 52] Enter a value to search for: 8 Found 8 at position 7 [20, 61, 72, 84, 28, 56, 11, 5, 17, 74, 73, 30, 17, 1, 66, 6, 76, 53, 74, 53] Enter a value to search for: 10 10 is not in the Now let's write a for loop version:list.
Теперь давайте напишем версию цикла for:
def find(list, value):
for i in range(0, len(list)):
if list[i] == value:
return i
return -1There's really not much difference between the two functions, though most programmers would write this function with a for loop as for loops are the most natural way to traverse lists.
You can plug this function into the program above and you'll get similar results. The results won't necessarily be the same because the program uses random number generation for creating the lists.
в функции
Python предоставляет встроенную функцию in, которую можно использовать для определения того, содержит ли список значение. Вот шаблон синтаксиса для функции in:
Логическое значение данных в имени списка
Функция in не похожа на традиционную функцию и больше похожа на условный оператор в C++. Слева от ключевого слова in находится значение для поиска, а справа — список, который вы хотите найти. Если значение найдено в списке, функция возвращает True; в противном случае функция возвращает False.
Вот программа, которая демонстрирует, как использовать функцию in:
from random import randint
from random import seed
seed(1)
numbers = []
for i in range(1,11):
numbers.append(randint(1,100))
print(numbers)
value = int(input("Enter a number to search for: "))
if value in numbers:
print(value,"is in numbers.")
else:
print(value,"is not in numbers.")
Вот результат нескольких запусков этой программы:
[18, 73, 98, 9, 33, 16, 64, 98, 58, 61] Enter a number to search for: 33 33 is in numbers. [18, 73, 98, 9, 33, 16, 64, 98, 58, 61] Enter a number to search for: 15 15 is not in numbers.
Как всегда, вы должны использовать встроенные функции, предоставляемые языком, а не функции, которые вы пишете сами, но очень поучительно повторно реализовать функции языка с помощью собственного кода, чтобы стать лучшим программистом.
На этом статья о реализации шаблона Поиск в списке на Python завершена. Пожалуйста, не забудьте написать мне по адресу [email protected] с вашими комментариями и предложениями.
