何时使用"="在二进制搜索条件下?

问题描述

对于在二进制搜索中使用=的场景，我感到很困惑.例如，这是我从Wiki中找到的内容，它在(imin <= imax)

I am quite confused about the scenarios when to use the = in binary search. For example, this is what i found from wiki, in which it is using 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;
}

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

However, I also found a lot of code using something like

while (imin < imax)

我的问题是:使用=的关注点是什么?有什么原因吗?

My questions are: what's the concern to use the = or not? Any reason behind?

非常感谢！

推荐答案

请注意 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语句.正如Wiki所述:

You have three cases to consider, when imin < imax, imin == imax and imin > imax. The first algorithm deals with less than and equality within the while loop, whereas in the second algorithm, the equality case is deferred to the if statement. As wiki states:

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

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循环中使用<=还是仅使用<取决于您对实现的选择.

So the use of either <= in a while loop, or simply <, will depend on your choice of implementation.

这篇关于何时使用"="在二进制搜索条件下?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！