C++ 中的二进制搜索函数 returns 无限循环

Question

好吧，这更像是一个查询，所以我可以理解它在做什么，但是，我有下面的代码。实际上，while 循环会 return 一个无限循环，我将 while 更改为基本的 for(int i=0;i<n;i++) 循环，它可以正常工作并正确输出。

这是怎么回事？我实际上不知道为什么我的 while 循环会卡住，而 for 循环却不会。

bool binary_search(const string A[], int n, string name, int &count){
   count = 0;                  // Count initialization
   int fst = 0;
   int lst = n+1;              // First, Last and Middle array elements
   int mid = 0;

   while(fst<=lst)
   {
      count++;

      mid = (fst+lst)/2;      // Calculate mid point of array
      if (A[mid]==name)       // If value is found at mid
      {
         return true;
      }
      else if (A[mid]>name)
      {                       // if value is in lower
         lst = mid++;
         //cout << "elseIfME!" << endl;
      }
      else if (A[mid]<name)
      {                       // if value is in higher
         fst = mid--;
         //cout << "elseME!" << endl;
      }
   }
   return false;

}

Answer 1

您的条件应如下所示::

// Assuming that the array you are searching is sorted in descending order
// and hence the else-if conditions
else if (A[mid]>name)
{                       
   lst = mid + 1;
}
else if (A[mid]<name)
{      
   fst = mid - 1;
}

你用的post增量没用！因为，当你post增加（mid++和mid--）时，它returns原来的值（mid），那么这个值就是incremented/decremented，所以实际上，每次找不到该元素时，您都会在代码中设置 fst = mid 和 lst = mid。

所以，当 fst = lst 在二进制搜索期间将数组中的搜索域缩短为仅 1 个元素时，会计算 mid 等于 fst 和 lst，如果未找到该元素，您可以分配 fst = mid 或 lst = mid，因为这是您的循环应该停止的地方，并停止条件 fst <= lst 应该被违反，而这不是，因此是无限循环。

即使在搜索过程中，当您通过比较中心元素缩小搜索范围时，您也必须排除刚刚比较的中心元素，因为 post 增量，您不需要这样做！

如果你想让它工作，你也可以使用 pre-increment 和 pre-decrement！ (++mid 和 --mid)

Answer 2

我认为你的逻辑是倒退的。 if (A[mid]>name) 为真，则 name 位于列表的下半部分，但是您在超过这一点的中间增加，进入它不能位于的列表部分。在这种情况下，您应该设置 lst = mid-1，而不是 mid--，因为它将 lst 设置为 mid，然后将其递减。同样的测试if (A[mid]<name)，你应该设置fst = mid + 1，比如：

  else if (A[mid]>name)
  {                       // if value is in lower
     lst = mid - 1;
     //cout << "elseIfME!" << endl;
  }
  else if (A[mid]<name)
  {                       // if value is in higher
     fst = mid + 1;
     //cout << "elseME!" << endl;
  }

基本上，您的原始逻辑在确定值应该位于列表的哪个部分时会增加该部分的大小，而不是缩短它，因此您只需继续搜索更大的子列表，而不是更小的子列表。

C++ 中的二进制搜索函数 returns 无限循环

Binary Search Function in C++ returns infinite loop

c++

for-loop

binary-search

while-loop