Can someone please explain discrete binary search with an example?
I read about it on the above link, and got a basic idea about what it is, but I still don't understand the code part and how it is practically implemented.
Add a comment
|
1 Answer
Basically, assume that
- You have a function f(x) which is monotonically increasing (decreasing) on the interval [a, b].
- f(a) < C < f(b)
- You want to find x such that f(x) = C.
Then you can use binary search to find x. Essentially, you half the possible interval for the variable x each time.
To implement it, do something along the lines of:
#define EPS 1E-9
double f(double x)
{
///some monotonically increasing function on [a, b], for example f(x) = x^3:
return x*x*x;
}
double binarySearch(double C, double a, double b)
{
double low = a, high = b;
double mid;
while(abs(low-high) > EPS)
{
mid = low + (high - low) / 2;
if f(mid) < C
low = mid;
else
high = mid;
}
return mid;
}
8 Comments
riklund
In my opinion, it makes the code shorter and easier to understand.
Leonardo
For you, okay, but what about someone less experienced that doesn't know what epsilon is?
user3004790
Just to check if i got this right: Binary search is used for finding an element in a sorted array which is just a function,given interval (a,b). Discrete binary search uses the same idea/logic but not necessarily an array,but any monotonic function. Is it all..?
riklund
Yes, that's essentially it.
riklund
@Leonardo, I defined epsilon, so I assume that you refer to the concept. I still think that the intuitive way that the continuous case can be understood is much easier to explain than the discrete case. Then you never have to deal with off-by-one issues. But maybe that's just me.
|