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

Answers


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.

Post Status

Asked in February 2016
Viewed 2,118 times
Voted 8
Answered 2 times

Search




Leave an answer