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

我的問題是這樣的;給我想要做的事，這個代碼可以改進嗎？或者也許有更好的方式一起做這件事？顯然，通過提高容差來大大提高嘗試的次數 - 但這是以犧牲最終結果的準確性爲代價的。例如，在一定次數的嘗試後，增加容忍度對我來說是否合理？

此外，如何最好地確保所需數量在範圍內？我知道我可以在嘗試while循環之前確保!more(max) && more(min)，但是有沒有比在腳本的開頭部分簡單地插入兩個額外的檢查更有效的方法？

Answer 1

在二維搜索中搜索範圍內的數字很難做得更好。

假設範圍總是知道/相似，可以在search（）函數之前使用more（）函數或鉗位函數進行驗證。看到這個鏈接clamp number

如果範圍可以顯着變化，可以使用某種指數函數來找到'良好範圍'。

• 範圍0-100
• 範圍爲101〜1000
• 範圍1001〜20000
• 等

你也可以設置體貼你的寬容爲百分比，或作爲數'好小數'。 See here

知道你會得到同等的效力，同時尋找與X小數（即123.45的範圍爲0〜1000）中的號碼，而在一個範圍內尋找12345 0 100 000

由於'最壞情況'的嘗試次數是⌈log2（n + 1）⌉。 100次嘗試可以在0到n = 1267650600228229401496703205375範圍內找到一個數字。由於您有小數，所以您需要將該數字除以10得到的每個小數點。

A 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 

由於實數集緻密，應該明確的是，我們通常無法找到確切的目標值。但是，我們可以快速找到一些x，使得f（x）在no和yes之間的邊界的某個容忍範圍內。我們有兩種決定何時終止的方法：當搜索空間小於某個預定界限（比如10^-12）或者進行固定次數的迭代時終止。