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

              middle = (low + high)/2;          // Середина интервала
              if (А[middle] == value)      // Значение найдено –
                      return middle;       // вернуть индекс элемента
              if (А[middle] > value)
                      high = middle -1;        // Выбрать левую половину
              else low = middle +1;         // Выбрать правую половину
       }
       return -1;       // Значение не найдено
}

     Функция возвращает индекс найденного элемента или значение -1 если элемент не
найден. A[] - исходный массив, n - количество элементов, value - искомое значение.
     С небольшими изменениями данный алгоритм может использоваться для опреде-
ления места включения нового значения в упорядоченный массив. Для этого необходи-
мо ограничить деление интервала до получения единственного элемента (low == high),
после чего дополнительно проверить, куда следует производить включение.

int find_place (int A[], int n, int value)
{
        int low;          // Левая граница
        int high;           // Правая граница
        int middle;            // середина
        for(low = 0, high = n-1; low < high;) //while (low < high)
        {
                middle = (low + high)/2;            // Середина интервала
                if (А[middle] == value)       // Значение найдено –
                        return middle;        // вернуть индекс элемента
               if (А[middle] > value)
                        high = middle -1;          // Выбрать левую половину
               else low = middle +1;            // Выбрать правую половину
        }                // Выход по low == high
        if (value > A[low])
                return low+1; // Включить на следующую позицию
        return low;               // Включить на текущую позицию
}

      При двоичном поиске после первого сравнения интервал уменьшается в 2 раза, по-
сле второго - в 4 раза и т.д., таким образом, количество сравнений K будет не больше
соответствующей степени 2, дающей размерность массива N, т.е. 2K = N, K = log2(N).
Поэтому для массива из N = 1000 элементов количество сравнений K = 10, при N =
1000000 - K = 20 и т.д. Величина K называется трудоемкостью алгоритма. Трудоем-
кость - зависимость числа базовых операций алгоритма от размерности входных дан-
ных. Трудоемкость показывает не абсолютные затраты времени в секундах или минутах,
что зависит от конкретных особенностей компьютера, а в какой зависимости растет вре-
мя выполнения программы при увеличении объемов обрабатываемых данных. На
рис.2.2. приведены графики трудоемкости известных алгоритмов [10]:
- трудоемкость линейного поиска - N/2 - линейная зависимость;
- трудоемкость двоичного поиска - зависимость логарифмическая log2N ;
- для сортировки обычно используется цикл в цикле. Отсюда видно, что трудоемкость
   даже самой плохой сортировки не может быть больше N*N - зависимость квадратич-
   ная. За счет оптимизации она может быть снижена до N*log(N);


                                              44