Your answer is one click away!

shennan February 2016
### Implementing binary search with tolerance in JavaScript?

I'm trying to find a number between `min`

and `max`

. I only know (through using the `more`

method) whether the number I'm guessing is higher or lower than the number passed. The number that I need to find *can* be a decimal, which is what is making me nervous, as the average binary search seems to mostly concern itself with the business of integers.

The algorithm I've written is an attempt at a binary search, without the array. The difference, as I see it, between a classical binary search is that the values and the index of the search have been conflated into the same task.

```
var tolerance = 0;
var tries, min, max, current, needed;
function search () {
tries = 0;
min = 0;
max = 100;
needed = Math.random() * max;
current = (max - min) / 2;
while (!accept() && tries < 100) {
if (more(current))
min = current;
else
max = current;
current = min + ((max - min) / 2);
tries++;
}
results();
}
function more (n) {
return n < needed;
}
function accept () {
return Math.abs(current-needed) <= tolerance;
}
function results () {
document.getElementById('results').innerHTML = 'accepted: ' + current + '<br>needed: ' + needed + '<br>tries: ' + tries;
}
```

```
<button onclick="javascript:search();">search</button>
<br>
<div id="results"></div>
```

My question is this; given what I want to do, can this code be improved upon? Or perhaps there is a better way of doing this all together? Obviously, the number of tries is greatly improved by increasing the tolerance - but it's at the expense of the accuracy o

phenxd February 2016

It's hard to do better than a binary search for searching a number in a range.

Assuming the range will always be know/similar, validation can be done before the search() function either with the use of your more() function or a clamp function. See this link clamp number

If the range can change dramatically, some kind of exponential function could be used to find 'the good range'.

- Range 0-100
- Range 101 to 1000
- Range 1001 to 20000
- etc.

You could also considerate setting your tolerance as a percentage, or as a number of 'good decimals'. See here

Know that you will get the same efficacity while searching for a number with x decimals (ie. 123.45 in a range 0 to 1000) and while searching for 12345 in a range 0 to 100 000.

Since the 'worst case scenario' number of tries is ⌈log2(n+1)⌉. Having a 100 tries allows you to find a number precisely in a range of 0 to n = 1267650600228229401496703205375. Since you have decimals, for every decimal of precision you desire, you need to divide this number by 10.

A 0.xxxxxx precision would leave you with a 0 to 12676506002282294014967032 range in which you would find your number in less than 100 tries.

If my calculations are correct..

Rishav February 2016

When binary searching on a real interval, there is no need to check for equality, but instead you keep refining the search interval till it's sufficiently small.

```
// Generated by CoffeeScript 1.10.0
(function() {
var eps, hi, lo, mid, more, secret;
// This is your tolerance value.
eps = 0.01;
// The binary search routine will never get to see this.
secret = 45.63;
more = function(test) {
return test > secret;
};
lo = 0;
hi = 100;
while (hi - lo > eps) {
mid = lo + ((hi - lo) / 2);
if (more(mid)) {
hi = mid;
} else {
lo = mid;
}
}
console.log(mid);
}).call(this);
```

Output: `45.635986328125`

On out of range values, the output will be equal to `lo`

or `hi`

, where equal means that their absolute difference will be less than `eps`

.

See also: Binary searching on real numbers: Topcoder.

`binary_search(lo, hi, p): while we choose not to terminate: mid = lo + (hi-lo)/2 if p(mid) == true: hi = mid else: lo = mid return lo // lo is close to the border between no and yes`

Since the set of real numbers is dense, it should be clear that we usually won’t be able to find the exact target value. However, we can quickly find some x such that f(x) is within some tolerance of the border between no and yes. We have two ways of deciding when to terminate: terminate when the search space gets smaller than some predetermined bound (say 10^-12) or do a fixed number of iterations.

Asked in February 2016

Viewed 2,118 times

Voted 8

Answered 2 times

Viewed 2,118 times

Voted 8

Answered 2 times