c++ - C++ 中的二进制搜索函数返回无限循环

Question

好吧，这更像是一个查询，所以我可以理解它在做什么，但是，我有下面的代码。实际上，while 循环将返回一个无限循环，我将 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 increment没用!因为，当您发布增量( mid++ 和 mid-- )时，它返回原始值( mid )，然后该值递增/递减，所以实际上，您设置了 fst = mid和 lst = mid每次在您的代码中找不到该元素时。

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

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

如果你想让它工作，你也可以使用预递增和预递减! (++mid 和 --mid)