Java首先定位算法

int firstPosition(int x, int [] a) { 

    int lower = 0; 
    int upper = a.length; 

    while (lower != upper) { 
    int mid = (lower + upper)/2; 

    **if (x <= a[mid]) {** // the line I don't understand 
    upper = mid; 
    } else { 
    lower = mid + 1; 
    } 
    return (lower); 
}

如果a = {4，4，5，6，7，8，9，9，9}算法會返回以下選擇x？Java首先定位算法

I）中X = 3

ⅱ）X = 4

ⅲ）X = 5

IV），X = 9

V）X = 11

我嘗試過這個程序，例如x = 3，a.length返回10，所以upper總是等於10.

while (3 ! = 0) { // execute line 

int mid = lower + upper/2 - which is (0 + 10)/2 = 5 

if (x <= a[mid]) // I assume that means if 3 is less than or equal to 5? 5 then replace mid with 5 and then... 

lower = mid + 1 // 5+1 = 6, return 6 as lower?

來源

2011-05-27 Paradox

它看起來像二進制搜索。如果數組的中間元素更大，則降低中間值。 – 2011-05-27 19:15:09

這是一個基本的binary search算法，迭代而不是遞歸地實現。

您不理解的行檢查x（搜索值）是否可能位於數組的下半部分或上半部分。這是因爲數組已排序。我們可以把任何排序陣列分爲兩半，並期待在值在中間，以確定哪一半我們正在尋找可能的值

說，數組看起來像這樣：

+---+---+---+---+---+----+ 
| 1 | 3 | 5 | 7 | 9 | 11 | 
+---+---+---+---+---+----+ 
^     ^
    |      | 
lower     upper

我們試圖找出9這個數字在哪個插槽中。由於數組是排序的，我們可以立即丟棄數組的一半。

怎麼樣？

看在陣列的「中心」的價值：它是5，並9比5較大，因此我們知道9必須在陣列的上半部分。從算法上講，這將是代碼中的if語句的else大小寫。

因此，我們重複同樣的過程，但僅看陣列的上半這段時間：

+---+---+---+---+---+----+ 
| 1 | 3 | 5 | 7 | 9 | 11 | 
+---+---+---+---+---+----+ 
      ^  ^
       |   | 
      lower  upper

來源

2011-05-27 19:14:21

在我看來就像一個二進制搜索算法。 x的選擇確保每次迭代需要搜索的數組部分減半。閱讀更多關於它here

來源

2011-05-27 19:14:17

那麼如果x = 3，那麼回報6呢？ – Paradox 2011-05-27 19:15:45

'lower'是一個變量，而不是一個函數/方法，所以它不會「返回」任何東西， – 2011-05-27 19:17:34

是的，因爲數組長度等於10，所以'mid'等於5.當3 <5時，'lower'變成'中期+ 1'。因此'lower'變成了6 – 2011-05-27 19:19:04

這是一個二進制搜索的修改。

由於數據是有序的，所以要確定是否可以丟棄數據範圍的「上」或「下」一半，請查看中間元素。當它大於你要查找的數字時，你可以安全地丟棄超過它的數字（通過減小範圍）。當它小於要查找的數量時，可以安全地丟棄它之前的數字（通過減小範圍）。

這裏的關鍵是，如果它是你正在尋找的數字，你需要爬回到範圍的開始，直到你發現「下一個」數字實際上不是可能重複的「第一」值。

來源

2011-05-27 19:17:24

Java首先定位算法

回答

相關問題