binary-search - 什么时候在二分查找条件下使用 "="？

Question

我对何时使用 = 的场景感到很困惑。在二分查找中。例如，这是我从 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 语句。正如维基所说:

The iterative and recursive versions take three paths based on the key comparison: one path for less than, one path for greater than, and one path for equality. (There are two conditional branches.) The path for equality is taken only when the record is finally matched, so it is rarely taken. That branch path can be moved outside the search loop in the deferred test for equality version of the algorithm.

The deferred detection approach foregoes the possibility of early termination on discovery of a match, so the search will take about log2(N) iterations. On average, a successful early termination search will not save many iterations. For large arrays that are a power of 2, the savings is about two iterations. Half the time, a match is found with one iteration left to go; one quarter the time with two iterations left, one eighth with three iterations, and so forth. The infinite series sum is 2.

The deferred detection algorithm has the advantage that if the keys are not unique, it returns the smallest index (the starting index) of the region where elements have the search key. The early termination version would return the first match it found, and that match might be anywhere in region of equal keys.

所以使用任一 <=在 while 循环中，或简单地 < ，将取决于您选择的实现方式。