什么时候在二分查找条件下使用“=”？

Question

我对何时使用=in 二进制搜索的场景感到非常困惑。例如，这是我从 wiki 中发现的，其中使用了 while(imin <= imax)

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
     int imid = midpoint(imin, imax);
  if (A[imid] == key) 
    return imid;
  else if (A[imid] < key)
     imin = imid + 1;
  else        
    imax = imid - 1; 
    }

  return KEY_NOT_FOUND;
}

但是，我也发现了很多使用类似的代码

while (imin < imax)

我的问题是：使用=或不使用有什么问题？背后有什么原因吗？

非常感谢！

Answer 1

请注意wiki上的这两种算法：

迭代二分查找：

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if (A[imid] == key)
        // key found at index imid
        return imid;
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else        
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}

具有延迟检测相等性的迭代二分搜索：

int binary_search(int A[], int key, int imin, int imax)
{
  // continually narrow search until just one element remains
  while (imin < imax)
    {
      int imid = midpoint(imin, imax);

      // code must guarantee the interval is reduced at each iteration
      assert(imid < imax);
      // note: 0 <= imin < imax implies imid will always be less than imax

      // reduce the search
      if (A[imid] < key)
        imin = imid + 1;
      else
        imax = imid;
    }
  // At exit of while:
  //   if A[] is empty, then imax < imin
  //   otherwise imax == imin

  // deferred test for equality
  if ((imax == imin) && (A[imin] == key))
    return imin;
  else
    return KEY_NOT_FOUND;
}

您有三种情况来考虑，当imin < imax，imin == imax和imin > imax。第一个算法处理 while 循环中的小于和相等，而在第二个算法中，相等情况被推迟到 if 语句。正如维基所说：

迭代和递归版本基于键比较采用三种路径：一种小于的路径，一种大于的路径，以及相等的路径。（有两个条件分支。）只有当记录最终匹配时才会采用相等的路径，因此很少采用。该分支路径可以在算法的等式版本的延迟测试中移动到搜索循环之外。

延迟检测方法放弃了在发现匹配时提前终止的可能性，因此搜索将需要 log2(N) 次迭代。平均而言，成功的提前终止搜索不会节省很多迭代。对于 2 的幂的大型数组，节省的时间约为两次迭代。一半的时间，只剩下一次迭代就找到了匹配项；四分之一的时间剩下两次迭代，八分之一的时间剩下三次迭代，依此类推。无穷级数和为 2。

延迟检测算法的优点是如果键不唯一，则返回元素具有搜索键的区域的最小索引（起始索引）。早期终止版本将返回它找到的第一个匹配项，并且该匹配项可能位于具有相同键的区域中的任何位置。

因此，是<=在 while 循环中使用还是简单地使用<将取决于您选择的实现。