Вещественнозначный бинарный поиск (реализация на языке C++)

C++   9 Июль 2012  Автор статьи:  

Реализуем функцию, которая будет реализовывать бинарный поиск для неубывающей функции f, т.е. находить такой x, что f(x) = C, где C заранее заданное значение функции.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <fstream>
using namespace std;
double f(double x)//функция f, которую нужно переписать
{
    return x;
}
double binarySearch(double l, double r, double C, double e)//код бинарного поиска
{
    while (r - l > e)//пока не достигнута необходимая точность
    {
        double med = (l+r)/2;
        if (f(med) < C)
        {
                l = med;
        }
        else
        {
                r = med;
        }
    }
    return (l+r)/2;//улучшает ответ
}
int main()
{
    cout << binarySearch(-100000000,10000000,100301,0.00005);
    return 0;
}

Вещественный бинарный поиск выполняет бинарный поиск на достаточно крупном отрезке, пока разница между левым и правым значением отрезка, на котором осуществляется бинарный поиск не станет меньше, чем величина e, которой задается точность вычислений.
Такая реализация бинарного поиска может работать достаточно долго при некоторых входных данных. Гораздо проще задавать не константу, которая будет показывать точность вычислений, а задать конечное количество шагов вещественного бинарного поиска. Это возможно, так как любой тип хранит в себе конечное множество значений, но каждый раз отрезок поиска сокращается вдвое, таким образом выполнив 100 — 200 операций бинарного поиска мы упремся в ограничение типа данных, т.е. не сможем получить более точное значение. В связи с этим, можно преобразовать нашу функцию:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double binarySearch(double l, double r, double C, double e)//код бинарного поиска
{
    for(int i = 0;i < 100;i++)//заменили проверку точности на цикл
    {
        double med = (l+r)/2;
        if (f(med) < C)
        {
                l = med;
        }
        else
        {
                r = med;
        }
    }
    return (l+r)/2;
}

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

  • на Delphi

  • на Java

  • на C++