Поиск информации

заданным свойством?

Большинство задач поиска сводится к поиску в таблице элемента

с заданным значением.

Значение элемента х вводится с клавиатуры.
Решение:
Дано:
Const n= 10;
Var a:

Array[1..n] of integer;
x: integer;

информации о нем или о массиве, в котором его надо

искать, нет. Поэтому для решения задачи разумно применить последовательный просмотр массива и сравнение значения очередного рассматриваемого элемента с данным. Если значение очередного элемента совпадает с х, то запомним его номер в переменной k.

For i:=1 to n do
if a[i] = x then k:=i;

раз, то найдено будет последнее из них;
после того, как

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

Прервем просмотр сразу же после обнаружения заданного элемента!

inc(i);
В результате:
либо будет найден искомый элемент, т.е. найдется такой

индекс i, что a[i] = x;
либо будет просмотрен весь массив, и искомый элемент не обнаружится.
Поскольку поиск заканчивается только в случае, когда i = n + 1 или когда искомый элемент найден, то из этого следует, что если в массиве есть несколько элементов, совпадающих с элементом х, то в результате работы программы будет найден первый из них, т.е. элемент с наименьшим индексом.

пошагового просмотра при различных значениях х;

модифицировать программу для поиска

элемента массива, равного х, с максимально возможным индексом.

в заголовке цикла записано достаточно сложное условие, которое проверяется перед

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

Для этого используем искусственный прием!

х, который будет являться барьерным. Тогда если в процессе работы

программы
a[n + 1] := x; i := 1;
While a[i] <> x do inc(i);
обнаружится такой индекс i, что a[i] = x, то элемент будет найден. Но если a[i] = x будет только при i = n + 1, то, значит, интересующего нас элемента в массиве нет.
В случае наличия в массиве нескольких элементов, удовлетворяющих заданному свойству, будет также найден элемент с наименьшим номером.

возможным индексом.

нет, то ускорить поиск нельзя.
Если же известна некоторая информация о

данных, среди которых ведется поиск, например, массив данных отсортирован, удается существенно сократить время поиска, применяя непоследовательные методы поиска.

деления.

При его использовании на каждом шаге область поиска сокращается вдвое.

неубывания чисел, то есть для любого k: 1 ≤

k < n: a[k-1] ≤ a[k].
Найти такое i, что a[i] = x или сообщить, что элемента х в массиве нет.

Если да, то ответ получен. Если нет, то возможны два

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

18 20 25
х = 6
Шаг 1.
Найдем номер среднего элемента:

Так как 6 < a[5]

3 5 6 8 12 15 17 18 20 25

элемента:

Аналогично:

Шаг 3. Рассматриваем два элемента

A[3] = 6! Его номер – 3

– индекс первого, а R – индекс последнего элемента рассматриваемой

части массива.

{на первом шаге – весь массив}
f:=

false; {признак того, что х не найден}
while ( L<=R) and not f do
begin
m:= (L + R) div 2;
if a[m] = x then f:= true { элемент найден.
Поиск надо прекратить}
else if a[m] < x then L:= m + 1 {отбрасывается левая
часть}
else R:= m – 1 {отбрасывается правая часть}
end
End;

Begin
a[0]:=x;

L:= 1; R:= n;
Repeat
m:= (L + R) div 2;
if L > R then m:=0
else if a[m] < x then L:= m + 1
else R:= m - 1
until a[m]= x;
ans:= m;
End;

(Списать в тетрадь. Добавить комментарий)

методом простого включения. Учитывая, что готовая последовательность, в которую надо

вставлять элемент, является упорядоченной, можно методом деления пополам определить позицию включения нового элемента в неё. Такой модифицированный алгоритм сортировки называется методом двоичного включения.
Написать программу, реализующую этот метод.