查找排序数组中大于目标的第一个元素 [英] Find the first element in a sorted array that is greater than the target

问题描述

在一般的二分查找中，我们寻找出现在数组中的值.然而，有时我们需要找到大于或小于目标的第一个元素.

In a general binary search, we are looking for a value which appears in the array. Sometimes, however, we need to find the first element which is either greater or less than a target.

这是我丑陋且不完整的解决方案:

Here is my ugly, incomplete solution:

// Assume all elements are positive, i.e., greater than zero
int bs (int[] a, int t) {
  int s = 0, e = a.length;
  int firstlarge = 1 << 30;
  int firstlargeindex = -1;
  while (s < e) {
    int m = (s + e) / 2;
    if (a[m] > t) {
      // how can I know a[m] is the first larger than
      if(a[m] < firstlarge) {
        firstlarge = a[m];
        firstlargeindex = m;
      }
      e = m - 1; 
    } else if (a[m] < /* something */) {
      // go to the right part
      // how can i know is the first less than  
    }
  }
}

对于这种问题，有没有更优雅的解决方案?

Is there a more elegant solution for this kind of problem?

推荐答案

考虑这个问题的一种方法是考虑对数组的转换版本进行二分查找，其中通过应用函数修改了数组

One way of thinking about this problem is to think about doing a binary search over a transformed version of the array, where the array has been modified by applying the function

f(x) = 1 if x > target
       0 else

现在，我们的目标是找到这个函数在值 1 上的第一个位置.我们可以使用二分查找来做到这一点，如下所示:

Now, the goal is to find the very first place that this function takes on the value 1. We can do that using a binary search as follows:

int low = 0, high = numElems; // numElems is the size of the array i.e arr.size() 
while (low != high) {
    int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
    if (arr[mid] <= target) {
        /* This index, and everything below it, must not be the first element
         * greater than what we're looking for because this element is no greater
         * than the element.
         */
        low = mid + 1;
    }
    else {
        /* This element is at least as large as the element, so anything after it can't
         * be the first element that's at least as large.
         */
        high = mid;
    }
}
/* Now, low and high both point to the element in question. */

要查看此算法是否正确，请考虑进行的每个比较.如果我们找到一个不大于目标元素的元素，那么它和它下面的所有元素都不可能匹配，所以没有必要搜索那个区域.我们可以递归搜索右半部分.如果我们发现一个元素比所讨论的元素大，那么它之后的任何元素也必须更大，所以它们不能是更大的第一个元素，所以我们不需要搜索他们.因此，中间元素是它可能出现的最后一个位置.

To see that this algorithm is correct, consider each comparison being made. If we find an element that's no greater than the target element, then it and everything below it can't possibly match, so there's no need to search that region. We can recursively search the right half. If we find an element that is larger than the element in question, then anything after it must also be larger, so they can't be the first element that's bigger and so we don't need to search them. The middle element is thus the last possible place it could be.

请注意，在每次迭代中，我们至少放弃了一半的剩余元素.如果 top 分支执行，那么 [low, (low + high)/2] 范围内的元素都被丢弃，导致我们失去 floor((low + high)/2) - low + 1 >= (low +高)/2 - 低 = (高 - 低)/2 个元素.

Note that on each iteration we drop off at least half the remaining elements from consideration. If the top branch executes, then the elements in the range [low, (low + high) / 2] are all discarded, causing us to lose floor((low + high) / 2) - low + 1 >= (low + high) / 2 - low = (high - low) / 2 elements.

如果底层分支执行了，那么[(low + high)/2 + 1, high]范围内的元素都被丢弃.这让我们失去了 high - floor(low + high)/2 + 1 >= high - (low + high)/2 = (high - low)/2 个元素.

If the bottom branch executes, then the elements in the range [(low + high) / 2 + 1, high] are all discarded. This loses us high - floor(low + high) / 2 + 1 >= high - (low + high) / 2 = (high - low) / 2 elements.

因此，我们最终会在此过程的 O(lg n) 次迭代中找到大于目标的第一个元素.

Consequently, we'll end up finding the first element greater than the target in O(lg n) iterations of this process.

这是在数组 0 0 1 1 1 1 上运行的算法的跟踪.

Here's a trace of the algorithm running on the array 0 0 1 1 1 1.

最初，我们有

0 0 1 1 1 1
L = 0       H = 6

所以我们计算mid = (0 + 6)/2 = 3，所以我们检查位置3处的元素，其值为1.由于1 > 0，我们设置high = mid = 3.我们现在有

So we compute mid = (0 + 6) / 2 = 3, so we inspect the element at position 3, which has value 1. Since 1 > 0, we set high = mid = 3. We now have

0 0 1
L     H

我们计算 mid = (0 + 3)/2 = 1，所以我们检查元素 1.因为它的值是 0 <= 0，我们设置 mid = low + 1 = 2.我们现在剩下 L= 2 且 H = 3:

We compute mid = (0 + 3) / 2 = 1, so we inspect element 1. Since this has value 0 <= 0, we set mid = low + 1 = 2. We're now left with L = 2 and H = 3:

0 0 1
    L H

现在，我们计算 mid = (2 + 3)/2 = 2.索引 2 处的元素是 1，并且由于 1 ≥0，我们设置 H = mid = 2，此时我们停止，实际上我们正在查看第一个大于 0 的元素.

Now, we compute mid = (2 + 3) / 2 = 2. The element at index 2 is 1, and since 1 ≥ 0, we set H = mid = 2, at which point we stop, and indeed we're looking at the first element greater than 0.

希望这有帮助！

这篇关于查找排序数组中大于目标的第一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！