Когда вы открываете веб-браузер, ищете страничку, информацию, друзей в соцсетях, вы совершаете поиск, точно так же, как при попытке найти нужную пару обуви в магазине.
Вы наверняка замечали, что упорядоченность сильно влияет на то, как вы ищете. Если у вас все рубашки лежат в шкафу, найти среди них нужную обычно проще, чем среди разбросанных без системы по всей комнате.
Линейный поиск — способ последовательного поиска, один за одним. Когда вы пересматриваете результаты поиска в 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 шагов.
Вы, вероятно, уже догадались, какой способ работает лучше для отсортированного массива?
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ