c++ - 使用二进制搜索搜索 vector 的上限

Question

给定一个输入(值 1)，我需要在 vector (“vec”)中找到它的上限。我需要返回指向此上限值的指针，而不是返回上限值。

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

如果我的输入值 1="13"，那么我的函数 upperBound() 应该返回指向元素 15 的指针。

upperBound() 函数返回“pointerUpperBound”——它是指向 value1 上限的指针。

在我的例子中，上限是指大于或等于输入值 (value1) 的值。是大于输入的最小数

 //**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;
   }
}

我的算法没有返回正确的上限。谁能帮我弄清楚我哪里出错了。

我只想使用“指针”遍历这个 vector 。我不想使用内置函数来查找上限——因为我想了解我的算法哪里出错了。

Answer 1

您没有仔细考虑请求值大于 vector 中任何值的情况，并且通过忽略该情况，您也弄错了其他情况。

您没有发布您测试的真实代码，因为:

  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
}

代码真的很简单。边界案例值得思考，但我认为它们都能解决。如果 vector 中的每个项目 < value1，此代码返回超过 vector 末尾的第一个位置。这是一个设计选择(不是对或错)。如果您不喜欢该选择，应该很容易更改。

在任何二分搜索中，你需要注意它总是收敛，永远不会陷入一个不改变的循环 l或 r什么时候r==l+1 .这是二进制搜索中一个非常普遍的缺陷，我在代码中评论了我认为它不会发生的原因。

那么您需要精确定义哪里l和 r点以查看边界情况是否安全。 l仅传递元素 <value1所以我们仍然确定它不会传递可能 ==value1 的第一个元素. r备份项目不是 <value1所以它可能会跨项目备份 ==value1所以在多个项目匹配的边界情况下 value1我们似乎找到了第一个。这是一个意外的“设计选择”，您可能愿意也可能不愿意更改。但除此之外，我们至少会看到 r从不备份项目 <value1