Двоичный поиск

Эту статью следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.

Двоичный поискалгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Основная идея заключается в том, что если такая функция в двух точках имеет один знак, то и на всех точках отрезка между ними она будет того же знака. Если мы ищем 0, то на концах отрезка она должна быть разных знаков. Теперь посмотрим на середину отрезка и ту из двух половин, на концах которого функция одного знака, отбросим. Таким образом длина отрезка, на котором мы должны искать значение, уменьшилась в 2 раза.

Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать 0 получившейся функции.

Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время log2α, где \alpha = {1\over \epsilon} Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + log2N времени.

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

Пример

Переменные L_b\,\! и U_b\,\! содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением U_b\,\! становится \left( M - 1 \right)\,\! и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй — до 255.Т.о. для поиска в массиве из 1023 элементов достаточно 10 сравнений.

int function BinarySearch (Array A, int Lb, int Ub, int Key);
  begin
  do forever
    M = (Lb + Ub)/2;
    if (Key < A[M]) then
      Ub = M - 1;
    else if (Key > A[M]) then
      Lb = M + 1;
    else
      return M;
    if (Lb > Ub) then
    return -1;
  end;


Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home