Вещественный двоичный (бинарный поиск) или двоичный поиск для монотонной функции
Двоичный поиск может использоваться не только для поиска элементов в массиве, но и для поиска корней уравнений и значений монотонных (возрастающих или убывающих) функций.
Пусть нам задана монотонная функция f и какое-то значение C этой функции. Необходимо найти значение аргумента x этой функции, такое, что \(f(x)=C\).
Пример возрастающей монотонной функции:
Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Но есть проблема в том, что, когда остановить поиск. Способо закончить поиск подробно описаны здесь.
Для примера рассмотрим задачу поиска квадратного корня числа x. Квадратным корнем из числа x (обозначается \(\sqrt x\)) называется такое число y, что \(y^2 = x\).
Сформулируем задачу так: для данного вещественного числа x ( \(x >= 1\)) найти квадратный корень с точностью не менее 5 знаков после точки.
Выбор границы отрезка для поиска
Так как мы не можем проверять всю бесконечность чисел, надо обозначить границы поиска корня. Для начала найдем левую границу, выберем произвольную отрицательную точку (например: -1). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например: 1). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Мы же в своих примерах будет останавливать поиск, когда рассматриваемый отрезок станет меньше заданной погрешности eps.
double findLeftBoard(C : double):
x = -1
while f(x) > C
x = x * 2
return x
double findRightBoard(C : double):
x = 1
while f(x) < C
x = x * 2
return x
Либо, если мы точно знаем границы поиска, можем взять за левую границу 1, а верхнюю само число x.
После этого делим текущий отрезок пополам, возводим середину в квадрат и если он больше x, то заменяем верхнюю грань, иначе нижнюю.
Итоговая реализация:
double binSearch(C : double):
left = findLeftBoard(C) // начальный отрезок
right = findRightBoard(C)
while right - left > eps // сужаем отрезок поиска ответа до малого eps.
mid = (left + right) / 2
if f(mid) < C
left = mid
else
right = mid
return (left + right) / 2
|
Вещественный двоичный (бинарный поиск) или двоичный поиск для монотонной функции
Двоичный поиск может использоваться не только для поиска элементов в массиве, но и для поиска корней уравнений и значений монотонных (возрастающих или убывающих) функций.
Пусть нам задана монотонная функция f и какое-то значение C этой функции. Необходимо найти значение аргумента x этой функции, такое, что \(f(x)=C\).
Пример возрастающей монотонной функции:
Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Но есть проблема в том, что, когда остановить поиск. Способо закончить поиск подробно описаны здесь.
Для примера рассмотрим задачу поиска квадратного корня числа x. Квадратным корнем из числа x (обозначается \(\sqrt x\)) называется такое число y, что \(y^2 = x\).
Сформулируем задачу так: для данного вещественного числа x ( \(x >= 1\)) найти квадратный корень с точностью не менее 5 знаков после точки.
Выбор границы отрезка для поиска
Так как мы не можем проверять всю бесконечность чисел, надо обозначить границы поиска корня. Для начала найдем левую границу, выберем произвольную отрицательную точку (например: -1). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например: 1). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Мы же в своих примерах будет останавливать поиск, когда рассматриваемый отрезок станет меньше заданной погрешности eps.
def findLeftBoard(C):
x = -1
while f(x) > C:
x = x * 2
return x
def findRightBoard(C):
x = 1
while f(x) < C:
x = x * 2
return x
Либо, если мы точно знаем границы поиска, можем взять за левую границу 1, а верхнюю само число x.
После этого делим текущий отрезок пополам, возводим середину в квадрат и если он больше x, то заменяем верхнюю грань, иначе нижнюю.
Итоговая реализация:
def binSearch(C):
left = findLeftBoard(C) # начальный отрезок
right = findRightBoard(C)
while right - left > eps: # сужаем отрезок поиска ответа до малого eps.
mid = (left + right) / 2
if f(mid) < C:
left = mid
else:
right = mid
return (left + right) / 2
|