Алгоритмы линейного поиска. Тема 1

массиве А значение х. Если да, то мы хотим знать индекс i, такой, что A[i] = х. Если нет – вывести соответствующее сообщение. При этом x может встретиться в массиве более одного раза.
Алгоритм линейного поиска: мы начинаем с начала массива (первого его элемента), поочередно проверяя все его элементы (А[1] затем A[2], затем A[3] и так далее до А[n]) и записывая место, где мы находим x (если мы вообще находим его).

– количество элементов массива А, среди которых выполняется поиск;
• x – искомое значение.
Выход: значение переменной answer – либо индекс i, для которого A[i] = x, либо специальное значение not-found, которое может представлять собой любой некорректный индекс массива, например, произвольное отрицательное значение.
Шаги процедуры:
1. Установить значение answer равным not-found.
2. Для каждого индекса i, пробегающего поочередно значения от 0 до n-1:
А. Если A[i] = x, установить значение answer равным i.
3. В качестве выходного вернуть значение answer.

x.

Процедура Better-Linear-Search(A,n,x)
Вход и выход: те же, что и в Linear-Search.
Шаги процедуры:
1. Для i = 0 до n-1:
А. Если A[i] = х, вернуть значение i в качестве выхода процедуры.
2. В противном случае вернуть в качестве выходного значение not-found.

Для этого поместим искомое значение x в последнюю позицию А[n-1] после сохранения содержимого A[n-1] в другой переменной. Когда мы находим x, мы выполняем проверку, действительно ли мы его нашли или просто достигли конца цикла. Значение, которое мы помещаем в массив, называется ограничителем.

Процедура Sentinel-Linear-Search(A,n,x)
Вход и выход: те же, что и в Linear-Search.
Шаги процедуры:
1. Сохранить А[n-1] в переменной last и поместить х в А[n-1].
2. Установить i равным 0.
3. Пока А[i] ≠ x, увеличивать i на 1.
4. Восстановить А[n-1] из переменной last.
5. Если i < n-1 или A[n-1] = x, вернуть значение i в качестве выхода процедуры.
6. В противном случае вернуть в качестве возвращаемого значения not-found.