使用二進制搜索搜索矢量的上限

Question

給定一個輸入（值1）我需要在矢量（「vec」）中找到它的上限。我不需要返回上限值，而需要返回指向上限值的指針。

vector<int> vec; 
vec.push_back(5); vec.push_back(7); vec.push_back(15); 

如果我的輸入值1 =「13」，那麼我的函數UPPERBOUND（）應該返回指針元件15

UPPERBOUND（）函數返回「pointerUpperBound」 - 這是一個指向所述上值1的界限。

我的情況的上界意味着一個大於或等於輸入值（值1）的值。它是大於輸入的最小數字

//**GOAL OF ALGORITHM: Given "value1" it needs to find value1's upper bound in vector "vec". Instead of return the upper bound element, I need to return pointer to upper bound element** 
bool upperBound(int* &pointerUpperBound,int value1, vector<int> vec) 
    // Perform a binary search 
{ 
    unsigned left=0,right=(vec.size()-1); 
    int* l=&vec[0]; 
    int* r=(l+vec.size()-1); //l will be start of pageInfo vector and r will be end of page info vector 
    if(vec.size()==1) //vec has just one element in it. 
    { 
     pointerUpperBound=l; 
     return true; 

    } 
    while (left!=right) { 
     int* pointerUpperBound=l+((r-l)/2); 
     unsigned middle=left+((right-left)/2); 
     if(value> (*pointerUpperBound)) {  
     l=pointerUpperBound+1; 
     left=middle+1; 
     } else if (!middle) { //reached the upper bound, it is "pointerUpperBound" which is also returned. 
     break; 
     } else { 
     int* prev=pointerToUpperBound; 
     prev--; 
     if(value1 > (*prev)) { 
      break; 
     } else{ 
      right=middle; 
      r=pointerToUpperBound; 
     } 
     } 
    } 
    // Unsuccessful search? 
    if (left==right) { 
     return false; 
    } 
} 

我的算法沒有返回正確的上限。有人可以幫我弄清楚我哪裏錯了。

我只想用「指針」來遍歷這個向量。我不想使用內置函數來尋找上限 - 因爲我想知道我的算法出錯的地方。

Answer 1

你還沒有想過通過案例所要求的值大於向量中的任何值，並且忽略了這種情況，你也得到了其他情況。

您還沒有發佈測試你，因爲真正的代碼：

int* pointerUpperBound=l+((r-l)/2); 
    unsigned middle=left+((right-left)/2); 
    if(value> (*pointerUpperBound)) {  
    l=m+1; 

什麼是m？

所有冗餘工作（並行指針和無符號拷貝）只是混淆的來源。使用一個或另一個。

想想你的代碼（您作出上述修正後）：

if(value> (*pointerUpperBound)) {  
    l=pointerUpperBound+1; 
    left=middle+1; 
    } 

如果value > *r上面的代碼可以達到l=r+1;是你打算什麼的話？如果不是，你打算做什麼？

你認爲你在決賽中報道了什麼情況？

// Unsuccessful search? 
    if (left==right) { 
     return false; 
    } 

想想其中r==l+2和你想要的答案是r的情況。您嘗試使用位置l+1並且它太小，因此您設置了l=l+1+1;並且從不嘗試該位置，因爲它是r，但您只需結束循環並返回false即可。你從勝利的下巴搶奪失敗。

---

bool upperBound(int* &pointerUpperBound,int value1, vector<int> vec) 
    // Perform a binary search 
{ 
    int* l=&vec[0]; // Pointer to lowest that might be == value1 
    int* r=l+vec.size(); //Pointer PAST last value that might be < value1 

    while (l < r) { 
     int* m=l+((r-l)/2); // Notice m<r, m>=l 
     if(value1 > *m) {  
     l=m+1; // l always increases here 
     } else { 
     r=m; // m always decreases here 
     } 
    } 
    pointerUpperBound = l; // first position >= value1 
} 

的代碼是真是小巫見大巫。邊界案例值得思考，但我認爲它們都能解決問題。如果矢量< value1中的每個項都返回該向量末尾的第一個位置。這是一個設計選擇（不對或錯）。如果你不喜歡這個選擇，它應該很容易改變。

在任何二進制搜索中，您都需要小心它總是收斂，永遠不會陷入循環不變的l或r當r==l+1。這是二進制搜索中常見的缺陷，我在代碼中評論了我認爲它不會發生的原因。

然後，您需要精確定義其中l和r指向以查看邊界情況是否安全。 l只傳遞元素<value1，所以我們保證它不會傳遞可能爲==value1的第一個元素。 r備份項目不是<value1所以它可能備份到項目==value1所以在邊界情況下多個項目匹配value1我們似乎找到第一個。這是一個意外的「設計選擇」，你可能會也可能不想改變。但除此之外，我們至少看到r從不備份到一個項目<value1

Answer 2

貌似你試圖使用pointerUpperBound作爲輸出參數，但通過值傳遞。

調用者不會看到您對指針所做的修改。

傳遞參考。