基本二進制搜索上下限之間的區別？

Question

在文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch中，作者討論了二分查找。他區分找到某些事情是真的最低值和假的事物的最高值。 數組被搜索看起來類似：

假假假真真

我很好奇，爲什麼這兩種情況是不同的。爲什麼你不能找到真正的最低值，然後減去一個來找出最高的值是錯誤的？編輯2：好的，所以我理解更低的上限。現在，我在努力理解，當搜索大於或等於查詢的最小整數時，爲什麼我們不能將if(mid>query)更改爲if(mid>=query)，並讓它的值降低而不是上限。

編輯：下面是文章指出：

「現在，我們終於得到了實現在這個前面已經介紹和二進制搜索代碼：

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo)/2 
     if p(mid) == true: 
     hi = mid 
     else: 
     lo = mid+1 

    if p(lo) == false: 
     complain    // p(x) is false for all x in S! 

    return lo   // lo is the least x for which p(x) is true 

...

如果我們想找到最後x其中p（x）是假的，我們會設計（使用類似的原理同上）是這樣的：

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo+1)/2 // note: division truncates 
     if p(mid) == true: 
     hi = mid-1 
     else: 
     lo = mid 

    if p(lo) == true: 
     complain    // p(x) is true for all x in S! 

    return lo   // lo is the greatest x for which p(x) is false 

。「

Answer 1

二進制搜索的下限和上限是可以在不破壞順序的情況下插入值的最低和最高位置。 （在C++標準庫，這些邊界將被迭代引用值可以插入其中之前的元素表示，但概念基本上不改變。）

舉個例子來說，一個排序範圍

1 2 3 4 5 5 5 6 7 9 

在爲3二進制搜索，我們將有

v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
    ^-- upper bound 

而且在5二進制搜索：

 v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
      ^-- upper bound 

如果元素不在範圍內，則上下限相同。在爲8二進制搜索：

    v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
       ^-- upper bound 

到你提到的短語在相當於而言，這所有的文章的作者「小於」和「大於」以便在搜索5，

 v-- lower bound 
t t t t f f f f f f  <-- smaller than? 
1 2 3 4 5 5 5 6 7 9 
f f f f f f f t t t  <-- greater than? 
      ^-- upper bound 

在所有這些情況下，C++迭代器將引用直接位於邊界後面的元素。這就是說：

• 在尋找3，通過std::lower_bound返回的迭代器會參考3和std::upper_bound的人會參考4
• 在尋找5，通過std::lower_bound返回的迭代器會參照第一5和std::upper_bound的人會參考6
• 在尋找8，既要提到9

這是因爲用於插入的C++標準庫中的慣例是傳遞引用元素的迭代器，在該元素之前應該插入新元素。例如，

std::vector<int> vec { 1, 3, 4, 5, 5, 5, 6, 7, 9 }; 
vec.insert(vec.begin() + 1, 2); 

vec後，將包含1, 2, 3, 4, 5, 5, 5, 6, 7, 9。 std::lower_bound和std::upper_bound遵守這個約定讓

vec.insert(std::lower_bound(vec.begin(), vec.end(), 5), 5); 
vec.insert(std::upper_bound(vec.begin(), vec.end(), 8), 8); 

工作需要的和離開vec排序。

更一般地，這是C++標準庫中指定範圍方式的表達式。範圍的開始迭代器引用範圍的第一個元素（如果有的話），而結束迭代器引用該範圍末尾後面的元素（如果有的話）。另一種看待它的方式是由std::lower_bound和std::upper_bound返回的迭代器跨越搜索範圍中等於搜索元素的元素範圍。

這個範圍是空的，如果該元素不在範圍內，使lower_bound和upper_bound返回相同的迭代器，否則lower_bound返回一個迭代器，在搜索範圍內的第一個元素是等同於同時upper_bound搜索值返回一個指向最後一個元素後面的元素（如果有的話）的迭代器。如果你找到最低值，其中值是true和減去1：

Answer 2

如果陣列將永遠是

false … true … 

那麼一個你會發現永遠是假的，除非你在index 0找到真正的前指數。如上面我的評論所述，另一個邊界案例是，如果您沒有找到true。然後，最高的false將是數組的最後一部分。

Answer 3

這兩種算法中，如果有任何true或沒有false值從代碼片段其實是相當明顯的應發生什麼情況明顯不同從這個位置找到最高值產生false產生了不正確的結果，因爲沒有這樣的對象。由於算法只針對處理定位適當元素的不同元素而不是特殊情況，因此也避免了必須處理特殊情況，從而減少了代碼量。由於特殊情況代碼往往只對每個算法調用執行一次，因此它可能會比避免特殊情況稍差。這是值得衡量的事情。

請注意，代碼示例不是C++，儘管問題被標記爲C++。因此它不是慣用的C++。 C++中實現類似lower_bound()或upper_bound()的典型方法是使用適當的迭代器。如果沒有合適的元素，這些算法就不會「投訴」，因爲它們只是產生適當位置的迭代器，即迭代器爲std::lower_bound()的開始和std::upper_bound()的過去末端迭代器。