# Developers Planet

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`.

``````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.

#### Post Status

Asked in February 2016
Viewed 2,118 times
Voted 8