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

你使用的后增量是没用的!因为,当您发布的增量(mid++和mid--),它返回原来的值(mid),然后该值递增/递减,所以实际上,你设置fst = mid和lst = mid在你的代码,每次你没有找到的元素.

那么,fst = lst当二进制搜索期间你将数组中的搜索域缩短到只有1个元素时,你会计算出mid哪个等于fst和lst,如果找不到元素,你可以分配fst = mid或者lst = mid,因为这是你的循环应该停止,并且要停止fst <= lst违反条件,这不是,因此是无限循环.

即使在通过比较中心元素缩小搜索域的搜索过程中,您也必须排除刚刚比较的中心元素,而不是因为后期增量!

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