Когда вы открываете веб-браузер, ищете страничку, информацию, друзей в соцсетях, вы совершаете поиск, точно так же, как при попытке найти нужную пару обуви в магазине. 

Вы наверняка замечали, что упорядоченность сильно влияет на то, как вы ищете. Если у вас все рубашки лежат в шкафу, найти среди них нужную обычно проще, чем среди разбросанных без системы по всей комнате. 

Линейный поиск — способ последовательного поиска, один за одним. Когда вы пересматриваете результаты поиска в Google сверху вниз, вы используете линейный поиск.

Пример. пусть у нас есть список чисел:

2 4 0 5 3 7 8 1

И нам нужно найти 0. Мы его видим сразу, но компьютерная программа так не работает. Она начинает с начала списка и видит число 2. Затем проверяет, 2=0? Это не так, поэтому она продолжает работу и переходит ко второму символу. Там её тоже ждет неудача, и только на третьей позиции алгоритм находит нужное число.

Псевдокод линейного поиска: 

linearSearch(key, array[]):

	for(i = 0; i < length(array); i++):
		if(array[i] == key):
			return i 
	
return -1

Функция linearSearch получает на вход два аргумента — ключ key и массив array[].Ключ — искомое значение, в предыдущем примере key = 0. Массив — список чисел, которые мы будем просматривать. Если мы ничего не нашли, функция вернет -1 (позицию, которой в массиве нет). Если же линейный поиск найдет нужный элемент, то функция вернет позицию, на которой находится искомый элемент в массиве.

В линейном поиске хорошо то, что он будет работать для любого массива, независимо от порядка элементов: мы всё равно пройдём по всему массиву. Это же является и его слабостью. 

Если вам нужно найти число 198 в массиве из 200 чисел, отсортированных по порядку, цикл for пройдет 198 шагов. 

Линейный поиск - 1

Вы, вероятно, уже догадались, какой способ работает лучше для отсортированного массива?