Вещественнозначный бинарный поиск

Алгоритмы   6 июля 2012  Автор статьи:  

Вещественно значный бинарный поиск используется для решения многих задач, зависящих от непрерывной неубывающей (реже невозрастающей) функцией f(x), определенной на некотором отрезке [l,r]. Как правило для некоторой вещественнозначного С требуется найти такое x, что f(x) = C.
Пусть f(x) — непрерывная неубывающая функция. Если f(l) > C или f(r) < C, то однозначно можно утверждать что решения уравнения f(x) = C на отрезке [l,r] не существует. В другом случае мы бинарным поиском ищем такой отрезок, чтобы f(l) = C или f(r) = C. Так как решение может не быть двоичным рациональным числом, то точно представить решение в виде вещественного числа невозможно. Есть два варианта возможных действий: либо получить решения с заранее определенной погрешностью, либо получить решение максимально точно. В первом случае мы делим отрезок [l,r] до тех пор, пока |r-l|>e (е — заранее заданная точность). Во втором случае, любой вещественнозначный тип данных имеет число конечное число значений, то после некоторого определенного числа делений отрезка пополам, отрезок будет содержать единственное число, которое можно представить в машинном представлении. Это число и является максимально точным решением. Есть два варианта получения этого числа:

  1. Производить фиксированное число делений отрезка [l,r] пополам (100 делений достаточно для любых l и r для вычисления в типе данных doubel)
  2. производить деление отрезка [l,r] пополам до тех пор, пока med не станет равно l или r, где med — середина отрезка [l,r].

Это единственное, чем отличается вещественнозначный бинарный поиск от обычного, в остальном алгоритм аналогичен обычному бинарному поиску.

Научиться программировать

  • на Delphi

  • на Java

  • на C++