我必須檢查數字引起某種溢出類型的臨界點。找到一個符合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
有沒有更好的方法來做到這一點?
無法完全得到您。你能詳細說明你的方法嗎? –
使用二進制搜索類型算法可能是你最好的選擇在這裏(你已經完成,排序)從一些啓發式確定的數字開始可能比從1開始更好 – Chris
如果你不知道最大數目,我認爲用你最初的方法去找MIN = 64,MAX = 128的範圍是好的。之後,您應該簡單地進行二分搜索(例如,查看96,如果它導致溢出,那麼您知道範圍是MIN = 64,MAX = 96)。您在每一步都保持範圍,您會更快地找到解決方案。 –