對於缺失元素的二分查找是否總是在元素出現之前返回元素？

Question

這與C++中的lower_bound類似，用於二進制搜索的Javadoc也提到：「搜索關鍵字的索引，如果它包含在數組中;否則，（ - （插入點）-1）。」

我已經能夠驗證它是真的幾個例子，我敢肯定它是真的。但是，我無法證明這一點，所以我不確定。

我試圖通過矛盾做某種證明。它沿着線條運行：如果元素在那裏，那麼我們必須通過消除包含該元素的範圍來忽略它。潛在的位置和它應該處於的位置之間的差距必須很小。最後，如果有兩個元素，並檢查第一個元素，即元素或元素可能位置後面的元素。

我也試着去考慮減少存在的元素的情況下，沒有元素的情況下，但這種做法導致無處。我覺得我手揮着證據，抓着吸管。

問題中的陳述是否屬實？如果是這樣，你能證明嗎？

Answer 1

這取決於你如何實現二分搜索。

例如，像你描述的一種實現方法是讓它搜索大於或等於你的元素的第一個元素。然後，當二分查找停止時，停止的位置就是答案（實際元素或應該插入的位置）。

示例代碼：

binary_search(v: value to search, a: list to search in, n: list size): 
    left = 0, right = n 

    while left < right: 
     m = (left + right)/2 
     if a[m] >= v: // this is the important part: 
         // even if we find it, we continue, 
         // so we find the first such value. 
      right = m 
     else: 
      left = m + 1 

    return left 

實施例輸出：

binary_search(3, {1, 2, 4}, 3) = 2 
binary_search(0, {1, 2, 3}, 3) = 0 
binary_search(2, {1, 2, 3}, 3) = 1 

這應該是微不足道適應你提到的格式返回值。

對於實現here，我們可以證明它是這樣的：如果元素被找到，它的位置顯然會返回，所以我們關注未找到的情況。最終，二進制搜索循環將退出，因爲low == high + 1。

讓我們來看看如果在出口之前發現元素會發生什麼情況，例如考慮low = high = K。然後該元素將在位置K處找到。由於不是，我們將設置low = K + 1或high = K - 1。

由於元素沒有被發現，返回low會返回一個你感興趣的。