Если исходный массив ане упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а[1]. В худшем случае придется перебрать все n элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка n/2.
Классический алгоритм последовательного поиска включает следующие шаги:
- S1 Остановить начальный индекс равным 1 (j = 1).
- S2:Проверить условие q = a[j]. Если оно выполняется, то сообщить, что искомое значение находится в массиве а на j-ом месте и прервать работу. В противном случае продолжить работу.
- S3:Увеличить индекс j на 1.
- S4:Проверить условие j < n + 1. Если оно выполняется, то вернуться к шагу S2. В противном случае сообщить, что значение q в массиве а не содержится.
П р и м е р 13.Составить алгоритм и программу последовательного поиска, в которой возвращаемое значение либо равно индексу найденного элемента, либо равно — 1, если искомая величина в массиве не обнаружена.
