找到一個符合gt（大於條件）最快的數字的算法

我必須檢查數字引起某種溢出類型的臨界點。找到一個符合gt（大於條件）最快的數字的算法

如果我們假設溢出數爲98，那麼這樣做的一個非常低效的方法是從1開始並一次增加1。這將需要98次比較。

我衝出這樣做的更好的方式使

它通常做的改變檢查兩個已知故障狀態之後的下一個動力，例如，我們知道，0失敗，所以我們開始在檢查1，然後是2,4,8，...，128。 128次通過，所以我們檢查64 + 1,64 + 2,64 + 4，...，64 + 32，但是我們知道64 + 16失敗，所以我們開始下一輪1+（64 + 16）= == 1 + 80。這是一個視覺效果：

1 1 
2 2 
3 4 
4 8 
5 16 
6 32 
7 64 
81 128 -> 
9   1, 64 // 1 + 64 
10   2, 64 
11   4, 64 
12   8, 64 
13   16, 64 
14   32, 64 -> 
15     1, 80 
16     2, 80 
17     4, 80 
18     8, 80 
19     16, 80 
20     32, 80 -> 
21       1, 96 
22       2, 96 // done

有沒有更好的方法來做到這一點？

來源

2013-12-11 MosheK

無法完全得到您。你能詳細說明你的方法嗎？ –

使用二進制搜索類型算法可能是你最好的選擇在這裏（你已經完成，排序）從一些啓發式確定的數字開始可能比從1開始更好 – Chris

如果你不知道最大數目，我認爲用你最初的方法去找MIN = 64，MAX = 128的範圍是好的。之後，您應該簡單地進行二分搜索（例如，查看96，如果它導致溢出，那麼您知道範圍是MIN = 64，MAX = 96）。您在每一步都保持範圍，您會更快地找到解決方案。 –

如果你不知道最大數量，我想用你最初的方法去找MIN = 64，MAX = 128的範圍是好的。在找到最小/最大值後進行二分搜索將是最有效的（例如，查看96，如果它導致溢出，那麼您知道範圍是MIN = 64，MAX = 96）。您在每一步都保持減半，您會發現解決方案更快。

既然98是你的答案，這裏是它如何與二進制搜索泛型。這需要13個步驟，而不是22：

// your initial approach 
1 1 
2 2 
3 4 
4 8 
5 16 
6 32 
7 64 
8 128 -> 
// range found, so start binary search 
9   (64,128) -> 96 
10     (96,128) -> 112 
11       (96,112) -> 104 
12         (96,104) -> 100 
13          (96,100) -> 98 // done 
// you may need to do step 14 here to validate that 97 does not cause overflow 
// -- depends on your exact requirement

來源

2013-12-11 17:36:44

謝謝，我在下面的javascript中添加了一個implmentation – MosheK

如果您知道「溢出功能」是單調遞增的，你可以繼續加倍，直到你走了過來，然後應用經典的二進制搜索算法。這會給你下面的搜索順序：

1 
2 
4 
8 
16 
32 
64 
128 -> over - we have the ends of our range

運行在[64..128]範圍

64..128, mid = 96 
96..128, mid = 112 
96..112, mid = 104 
96..104, mid = 100 
96..100, mid = 98 
96..98, mid = 97 
97 - no overflow ==> 98 is the answer

來源

2013-12-11 17:37:19 dasblinkenlight

這裏的二進制搜索就是我如何實現在JavaScript這種技術：

function findGreatest(shouldPassCallback) { 
    function findRange(knownGood, test) { 
     if (!shouldPassCallback(test)) { 
      return [knownGood, test]; 
     } else { 
      return findRange(test, test * 2); 
     } 
    } 
    function binarySearchCompare(min, max) { 
     if (min > max) { 
      throw 'Huh?'; 
     } 
     if (min === max) { return shouldPassCallback(min) ? min : min - 1; } 
     if (max - min === 1) { return shouldPassCallback(max) ? max : min } 
     var mid = ~~((min + max)/2); 
     if (shouldPassCallback(mid)) { 
      return binarySearchCompare(mid, max); 
     } else { 
      return binarySearchCompare(min, mid); 
     } 
    } 
    var range = findRange(0, 1); 
    return binarySearchCompare(range[0], range[1]); 
}

來源

2013-12-11 19:20:15 MosheK

找到一個符合gt（大於條件）最快的數字的算法

回答

相關問題