在 JavaScript 中实现带公差的二进制搜索？

Question

我正在尝试查找 min 和 max 之间的数字。我只知道（通过使用 more 方法）我猜测的数字是高于还是低于传递的数字。我需要找到的数字可以是小数，这让我很紧张，因为平均二进制搜索似乎主要关注整数业务。

我写的算法是在没有数组的情况下进行二进制搜索的尝试。在我看来，经典二分搜索之间的区别在于搜索的值和索引已合并到同一任务中。

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>

我的问题是这样的；考虑到我想做的事情，可以改进这段代码吗？或者也许有更好的方法一起做这一切？显然，通过增加容忍度大大提高了尝试次数——但这是以牺牲最终结果的准确性为代价的。例如，在尝试一定次数后增加容忍度对我来说有意义吗？

此外，如何最好地确保所需的数量在范围内？我知道我可以确保 !more(max) && more(min) 在尝试 while 循环之前，但是有没有比在脚本开头简单地进行两次额外检查更有效的方法？

Answer 1

在搜索范围内的数字时，很难比二进制搜索做得更好。

假设范围始终为 know/similar，可以在 search() 函数之前使用您的 more() 函数或 clamp 函数进行验证。看到这个linkclamp number

如果范围可以显着变化，可以使用某种指数函数来找到 'the good range'。

范围 0-100
范围 101 到 1000
范围 1001 到 20000
等等

您也可以考虑将您的公差设置为百分比，或 'good decimals' 的数字。 See here

知道您在搜索具有 x 个小数位的数字（即 0 到 1000 范围内的 123.45）和在 0 到 100 000 范围内搜索 12345 时将获得相同的效果。

因为 'worst case scenario' 的尝试次数是⌈log2(n+1)⌉。尝试 100 次后，您可以精确地找到 0 到 n = 1267650600228229401496703205375 范围内的数字。由于您有小数，对于您想要的每个小数精度，您需要将该数字除以 10。

0.xxxxxx 精度会让您在 0 到 12676506002282294014967032 范围内尝试不到 100 次就可以找到您的号码。

如果我的计算是正确的..

Answer 2

在实数区间进行二分搜索时，无需检查相等性，而是不断细化搜索区间，直到足够小。

// 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);

输出：45.635986328125

对于超出范围的值，输出将等于 lo 或 hi，其中等于表示它们的绝对差将小于 eps。

另请参阅：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.

在 JavaScript 中实现带公差的二进制搜索？

Implementing binary search with tolerance in JavaScript?

javascript

math

binary-search

while-loop