Программирование на языке высокого уровня. Марапулец Ю.В. - 43 стр.

     Предлагаемый алгоритм называется линейным (последовательным) поиском, по-
тому что он просматривает по очереди все элементы, сравнивая их с искомым. Когда
данных немного, последовательный поиск работает достаточно быстро. Однако время
его работы прямо пропорционально количеству данных, которые нужно просмотреть;
удвоение количества элементов приведет к удвоению времени на поиск. Поэтому если
размерность массива сотни и тысячи элементов линейный поиск занимает продолжи-
тельное время. Тем более, что в реальных программах «элементами массива» являются,
конечно, не простые переменные, а более сложные образования (например, структури-
рованные переменные). Та часть элемента данных, которая идентифицирует его и ис-
пользуется для поиска, называется ключом. Остальная часть несет в себе содержатель-
ную информацию, которая извлекается и используется из найденного элемента данных.
     Ключ - часть элемента данных, которая используется для его идентификации и по-
иска среди множества других таких элементов. Приведенный выше фрагмент програм-
мы обеспечивает в неупорядоченном массиве последовательный, или линейный, поиск, а
среднее количество просмотренных элементов для массива размерности N будет равно
N/2.
     Можно использовать более оптимальные алгоритмы поиска, которые приведут к
уменьшению количества просмотренных элементов при поиске. Например, если элемен-
ты массива первоначально упорядочить, то для поиска элемента достаточно разбить
массив на две половины, выбрать из них ту, в которой находится искомый элемент, раз-
бить ее еще на две части и т.д. Такой алгоритм поиска называется двоичным поиском.
Однако для его реализации необходима предварительная проверка на упорядоченность
массива. Функция проверки упорядоченности массива служит живой иллюстрацией тео-
ремы: массив упорядочен, если упорядочена любая пара соседних элементов.

int Check_order (int a[], int n)
{
       for (int i=0; ia[i+1])
                return 0;
       return 1;
}

       Таким образом, если функция возвращает 1 - массив упорядочен, если 0 - нет.
       Алгоритм двоичного поиска выражается следующей последовательностью шагов:
- искомый интервал поиска делится пополам, и по значению элемента массива в точке
     деления определяется, в какой части следует искать значение на следующем шаге
     цикла;
- для выбранного интервала поиск повторяется;
- при «сжатии» интервала в 0 поиск прекращается;
- в качестве начального интервала выбирается весь массив.
       Следующий пример исходного кода демонстрирует алгоритм двоичного поиска в
упорядоченном массиве.

int binary_search (int А[], int n, int value)
{
        int low;        // Левая граница
        int high;         // Правая граница
        int middle;          // середина
        for(low = 0, high = n-1; low <= high;) //while (low <= high)
        {

                                             43