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

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作为输出参数，但通过值传递。

调用者不会看到您对指针所做的修改。

传递参考。