Представим себе обыкновенную ситуацию: у нас есть список, содержащий в себе множество элементов, например, строки.

Нам требуется найти индекс какого-нибудь элемента, и мы ничего не знаем о порядке элементов в списке.

Для начала предлагаю написать свое решение, а потом сравнить. Так будет интереснее.

В качестве примера возьмем часть ряда клавиш с клавиатуры.

a = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p']

Создадим функцию, которая будет принимать список и искомое значение, индекс которого нужно будет вернуть.

def linear_search(lst, x):
	pass

Условимся, что будем двигаться по списку слева-направо, как и в реальной жизни, если бы искали книги на полке.

Самый простой алгоритм (и самый неправильный), который приходит в голову - это создать переменную result, которой заранее присвоим значение None, а далее в цикле for пройтись по всем индексам и сравнить элементы с искомым значением (lst[index] = x), и если данное условие выполняется, то result = index.

def linear_search_1(lst, x):
	result = None
	for index, string in enumerate(lst):
		print(index, string)
		if string == x:
			result = index
	return result

print('='*10, linear_search_1(a, 'y'), sep='\n')

Процедура всегда возвращает правильный ответ, так почему она неэффективна?

Как многие догадались, поиск в массиве будет продолжаться, даже после нахождения искомого индекса. Если запустим скрипт, то output будет следующим:

0 q
1 w
2 e
3 r
4 t
5 y
6 u
7 i
8 o
9 p
==========
5

Не самое элегентное решение, тем более, если элементов в списке будет очень много.

Теперь сделаем так, чтобы поиск прекращался, как только мы найдем значение x.

def linear_search_2(lst, x):
	i = 0
	while i < len(lst) and lst[i] != x:
		print(i)
		i += 1
	return i if i < len(lst) else None

print('='*10, linear_search_2(a, 'y'), sep='\n')

Если мы находим x, то цикл сразу прерывается, если же мы ничего не находим, то получаем None:

0
1
2
3
4
==========
5

Но смущает то, что процедура выполняет по 2 проверки на каждой итерации - не вышли ли мы за границы списка и проверка равенства.

Опять же вернемся к книжным полкам, вы каждый раз смотрите на книгу, проверяете ее название и то, не дошли ли вы до конца полки? У всех умные девайсы и читалки

Проще говоря, условие i < len(lst) из while надо бы убрать.

Поместим элемент x в конец списка и будем точно уверены, что найдем искомый индекс. Если мы найдем “заменитель” (его еще называют ограничителем или барьером), то x в списке нет.

def linear_search_3(lst, x):
	lst.append(x)
	i = 0
	while lst[i] != x:
		print(i)
		i += 1
	return i if i < len(lst) - 1 else None

print('='*10, linear_search_3(a, 'y'), sep='\n')

Ну и в конце напишем тесты, чтобы спать спокойно. Пишите свои предложения, если я что-то пропустил.

class TestLinearSearch(unittest.TestCase):
	
	def setUp(self):
		self.lst = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p']
	
	def assertFunctions(self, *args, **kwargs):
		for func in args:
			result = func(self.lst, kwargs['str2find'])
			self.assertEqual(result, kwargs['index2find'], 'Problem with %s function' % func.__name__)

	def testMiddle(self):
		self.assertFunctions(linear_search_1, linear_search_2, linear_search_3, str2find='t', index2find=4)

	def testNotIn(self):
		self.assertFunctions(linear_search_1, linear_search_2, linear_search_3, str2find='1', index2find=None)

	def testEnd(self):
		self.assertFunctions(linear_search_1, linear_search_2, linear_search_3, str2find='p', index2find=9)

Код можно найти здесь.

Интересно? См. Бинарный (двоичный) поиск