對於k

Question

的第一次出現的二進制搜索我有代碼，搜索一個排序後的數組，並返回k的第一次出現的索引。 我想知道是否它可以編寫使用

while(left<right) 

，而不是

while(left<=right) 

下面這段代碼是全碼：

public static int searchFirstOfK(List<Integer> A, int k) { 
    int left = 0, right = A.size() - 1, result = -1; 
    // A.subList(left, right + 1) is the candidate set. 
    while (left <= right) { 
     int mid = left + ((right - left)/2); 
     if (A.get(mid) > k) { 
     right = mid - 1; 
     } else if (A.get(mid) == k) { 
     result = mid; 
     // Nothing to the right of mid can be the first occurrence of k. 
     right = mid - 1; 
     } else { // A.get(mid) < k 
     left = mid + 1; 
     } 
    } 
    return result; 
} 

我如何知道何時使用左邊是小於或等於正確的，或者只是使用左邊是不正確的。

Answer 1

大廈：How can I simplify this working Binary Search code in C?

如果你想找到第一個出現的位置，你不能當你找到一個匹配的元素停止。您的搜索應該是這樣的（當然這個假設列表進行排序）：

int findFirst(List<Integer> list, int valueToFind) 
{ 
    int pos=0; 
    int limit=list.size(); 
    while(pos<limit) 
    { 
     int testpos = pos+((limit-pos)>>1); 

     if (list.get(testpos)<valueToFind) 
      pos=testpos+1; 
     else 
      limit=testpos; 
    } 
    if (pos < list.size() && list.get(pos)==valueToFind) 
     return pos; 
    else 
     return -1; 
} 

請注意，我們只需要做好每次迭代一個比較。二進制搜索找到所有前面的元素都小於valueToFind且以下所有元素都大於或等於的唯一位置，然後然後它檢查您正在查找的值是否實際存在。

鏈接的答案突出了以這種方式編寫二進制搜索的幾個優點。

Answer 2

簡而言之號

考慮僅具有一個元件陣列的情況下，即，{0}和要搜索的元件是0爲好。

在這種情況下，left == right，但是如果您的條件是while(left<right)，那麼searchFirstOfK將返回-1。

---

這個答案是在發佈代碼的情況下。如果我們談論的替代品，這樣我們就可以使用while(left<right)然後馬特TIMMERMANS的答案是正確的，是一個更好的辦法。

下面是馬特的comparison（OP - 我們稱之爲普通二進制）和馬特TIMMERMANS（我們稱之爲優化的二進制）接近含有0 500萬之間和值的列表：

Answer 3

這是一個非常有趣的問題。事情是有一種方式，你可以使你的二進制搜索權始終。事情是確定正確的範圍並避免單個元素伸出行爲。

while(left+1<right) 
{ 
    m = (left+right)/2; 
    if(check condition is true) 
     left = m; 
    else 
     right = m; 
} 

只記住關鍵的是你總是讓左爲最小的條件不令人滿意元素，右爲最大的條件滿足的元素。這樣你就不會卡住了。一旦你瞭解了這種方法的範圍劃分，你將永遠不會在二分搜索中失敗。

以上初始化會給你最大的滿足條件的元素。

通過改變初始化，你可以得到各種元素（如小狀況令人滿意的元素）。這個答案，另一個二分查找問題