等於在二進制搜索中的意義

我正在C++中實現二進制搜索。這裏是我的代碼：等於在二進制搜索中的意義

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

int bs(vector<int> a, int val) 
{ 
    int l =0, r = a.size()-1; 
    while(l<=r) // Significance of == 
    { 
     int mid = l + (r-l)/2; 

     if(a[mid]==val) return mid; 
     if(a[mid]>val) 
     { 
      r = mid-1; continue; 
     } 
     else 
     { 
      l = mid + 1 ; 
     } 
    } 
    return l; // Deliberately returning this 
} 

int main() 
{ 
    vector<int> a = {1,3}; 
    cout << bs(a,1) <<endl; 
    return 0; 
}

問題1

在一些實現中，我看到人們使用

while(l<r)

而在一些他們使用

while(l<=r)

是否有任何偏好單向的概念區別？任何可能的錯誤來源，如果我不使用==？

問題2

萬一元素沒有被發現，爲L保證在該元素可以被插入，使得列表仍然排序的位置？這是有效的，而使用等於或不等於？

來源

2015-07-11 Martin Lampard

爲什麼downvote，這是一個很好的問題，我展示了我的嘗試。 –

'while（l

這取決於你如何計算變量r。在你的情況

r = a.size()-1;

所以，正確的用法是while(l<=r)

如果計算R爲r = a.size();正確的用法是while(l<r)

萬一元素沒有被發現，爲l保證是位置其中可以插入元素以便列表仍然保留排序？

您沒有對您的矢量進行排序，對於正確的二進制搜索，在調用二進制搜索之前，應對矢量進行排序。

std::sort(std::begin(a),std::end(a));

和頭提供std::binary_search，所以不是重新發明輪子，你可以按如下方式使用它：

std::binary_search(std::begin(a),std::end(a),val);

二進制搜索應該在矢量收益指數的價值，如果它發現。但是不能保證它應該提供下一個插入位置。

使用等於還是不等於？

我在我的答案的第一部分解釋了它。

來源

2015-07-11 10:37:26 Steephen

Plz非常感謝。那麼，在這種情況下，list [r]將被排除在搜索之外？ PLZ也看到問題2。 Merci。 –

@MartinLampard我編輯了我的答案 – Steephen

等於在二進制搜索中的意義

回答

相關問題