Конспект лекций по программированию для начинающих. Гладков В.П. - 170 стр.

                                        172

             readln(b[i])
       end;
       write('Введите искомый элемент ');
       readln(a);
       b[n+1]:=a; {добавили барьер, равный а, в конец массива}
       i:=1; { начинаем просмотр с первого элемента }
       while b[i]<>a do i:=i+1;
       { просматриваем массив, пока не найдем }
       if i<=n { вывод результатов поиска }
       then write('Номер найденного элемента ',i)
       else write('Не нашли')
    end.
    Тестирование.
    Тест 1. n=8, B[1]=2, B[2]=8, B[3]=3, B[4]=1, B[5]=9, B[6]=2, B[7]=2, B[8]=2,
B[9]=5, a=5. Результат поиска: «Не нашли».
    Тест 2. n=7, B[1]=2, B[2]=8, B[3]=3, B[4]=1, B[5]=9, B[6]=8, B[7]=2, B[8]=8, a=8.
Результат поиска: «Номер найденного элемента 2».
    Упражнения:
    1. Проведите трассировку и запомните оба варианта поиска.
    2. Напишите программы поиска, в которых элементы массива перебираются от
конца к началу.
    Вариант 3 (поиск методом деления пополам, или двоичный поиск).            Поиск
элемента в одномерном массиве можно значительно ускорить, если
предварительно упорядочить (отсортировать) массив. Для поиска массив делится
пополам и для сравнения выбирается средний элемент. Если он совпадает с
искомым, то поиск заканчивается. Если средний элемент меньше искомого, то все
элементы, расположенные левее его, также будут меньше искомого.
Следовательно, их можно исключить из дальнейшего поиска, оставив только
правую часть массива. Если средний элемент больше искомого, то отбрасывается
правая часть, а остается левая. Далее повторяется процедура деления массива
пополам и отбор части массива для дальнейшего поиска. Так продолжается до тех
пор, пока искомый элемент не будет найден или длина части массива для поиска не
станет равной нулю. Каждый раз величина той части массива, где ведется поиск,
уменьшается вдвое. Поэтому максимальное число требующихся сравнений равно
]log2N[, где N - количество элементов в массиве.
    Рассмотрим пример двоичного поиска.
    Искомый элемент a=7. Исходный массив n=16.
    Первый шаг поиска:
       номер элемента: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16;
       массив B={ 1, 3, 5, 6, 7,10,12,14,15,16,20,21,23,25,26,30 };
       начальная граница поиска L=1, конечная граница поиска R=16;
       середина части поиска i=(L+R) div 2 = 8;
    поскольку B[8]=14>a=7, то отбрасываем правую часть: L=1, R=i-1=7.
    Второй шаг поиска:
       номер элемента: 1 2 3 4 5 6 7;
       массив B={ 1, 3, 5, 6, 7,10,12 };