Двоичный поиск
Материал из Википедии — свободной энциклопедии
Эту статью следует викифицировать. Пожалуйста, оформите её согласно общим правилам и указаниям. |
Двоичный поиск — алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Основная идея заключается в том, что если такая функция в двух точках имеет один знак, то и на всех точках отрезка между ними она будет того же знака. Если мы ищем 0, то на концах отрезка она должна быть разных знаков. Теперь посмотрим на середину отрезка и ту из двух половин, на концах которого функция одного знака, отбросим. Таким образом длина отрезка, на котором мы должны искать значение, уменьшилась в 2 раза.
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать 0 получившейся функции.
Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время log2α, где Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + log2N времени.
В качестве примера можно рассмотреть поиск значения монотонной функции, записанной в массиве, заключающийся в сравнении срединного элемента массива с искомым значением, и повторением алгоритма для той или другой половины, в зависимости от результата сравнения.
[править] Пример
Переменные и содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением становится и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.
Например, если длина массива равна 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;