Implementing binary search with tolerance in JavaScript?

Question

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 of the final result. For example, would it make sense for me to increase the tolerance after a certain number of tries?

Also, how best would one go about ensuring that the needed number is in range? I know I could ensure that !more(max) && more(min) before attempting the while loop, but is there a more efficient way than simply bolting on two extra checks at the beginning of the script?

I would change the accept function to `Math.abs(current-needed) <= tolerance` just for better readability. — Wikunia, Feb 08 '16 at 18:58
Possible duplicate of [JavaScript - Binary search hangs every time](http://stackoverflow.com/questions/35193520/javascript-binary-search-hangs-every-time) — xrisk, Feb 08 '16 at 19:06
@Rishav This doesn't hang. My main question here is, can this be improved upon or are there better ways of achieving the same goal? — shennan, Feb 08 '16 at 19:09
You might get better feedback from http://codereview.stackexchange.com/ — Dave, Feb 08 '16 at 19:10
What do you want to happen if the number is out of range? Broaden the search? — phenxd, Feb 08 '16 at 19:10
@phenxd if the number is out of range then I'd like it to settle on either of the original `max` or `min` values, depending on which side of the range it falls. — shennan, Feb 08 '16 at 19:11
@phenxd do you mean, implement two checks using the `more` method at the beginning of each search? — shennan, Feb 08 '16 at 19:13
@dave thanks, I will try that tomorrow if the response here is poor. never knew about that stack exchange site. — shennan, Feb 08 '16 at 19:13
Personnally, I'd rather validate that the number is in range before executing the search function. And you can use your more() function if you want, of course, but you could also use a clamp function such as (see link) http://stackoverflow.com/questions/11409895/whats-the-most-elegant-way-to-cap-a-number-to-a-segment — phenxd, Feb 08 '16 at 19:15
@shennan binary search _always_ works, just look at that code. — xrisk, Feb 08 '16 at 19:21
@Rishav ditto, I'm not using an array for the search. The index and the value in my search are conflated. — shennan, Feb 08 '16 at 19:26
@shennan wait a minute.... you want to check whether a number is in between two other numbers? O.o What is the need of binary search there? — xrisk, Feb 08 '16 at 19:29
@Rishav I think you've misread the question and the code. If I've not been verbose enough then I apologise but other people have shown signs of understanding. Thanks for your suggestions anyway. — shennan, Feb 08 '16 at 19:30
@shennan alright then, can you clarify your question. More specifically, since you are already generating a number between `min` and `max` (at least in this snippet), what is the purpose of this search? And if the number you are generating is truly random and you wish to check if it is within `min` and `max`, then what is wrong with something like `if (min <= needed && needed <= max)` ? — xrisk, Feb 08 '16 at 19:33
@Rishav the range checks are (in theory) external to the code base. I will be guessing numbers to an external API, so I will not have the `needed` variable in practise. It's exposure in this script is purely to demonstrate the idea. — shennan, Feb 08 '16 at 19:35
@shennan alright, so you don't have the `needed` variable, but you do have access to a `more` function that will tell you whether said `needed` variable is greater than some input? Then using only this `more` function, you wish to check whether `needed` is in range? — xrisk, Feb 08 '16 at 19:38
@Rishav Using the `more` function, I wish to check whether `current` is within said `tolerance` of the `needed` number. Basically, as close as I can get to the decimal before a break clause is implemented. — shennan, Feb 08 '16 at 19:41
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/102932/discussion-between-rishav-and-shennan). — xrisk, Feb 08 '16 at 19:42

score 0 · Accepted Answer · edited May 23 '17 at 11:50

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

Thanks. Just to clarify, would you say that the code I've written (after your suggestion of the clamp check at the beginning) is a relatively solid implementation of a binary search? — shennan, Feb 08 '16 at 19:39
This answer has been the most helpful, and it's interesting to see the calculations you've outlined. Thanks. — shennan, Feb 09 '16 at 11:08

xrisk · Answer 2 · 2016-02-08T20:52:25.357

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.

This breaks when eps is zero, which I think is a lesser implementation. I prefer an implementation that breaks the loop after a certain amount of tries. That way, if the number is guessable within a certain number of steps, it'll be bang-on point. Thanks for putting the time in though, others may find this useful. — shennan, Feb 09 '16 at 11:11

Implementing binary search with tolerance in JavaScript?

2 Answers2