在排序数组中找到大于目标的第一个元素 [英] 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. */

要查看该算法是否正确，请考虑进行每个比较。如果我们发现一个元素不大于目标元素，则该元素及其下方的所有内容可能都不匹配，因此无需搜索该区域。我们可以递归搜索右半部分。如果我们发现一个大于所讨论元素的元素，那么它后面的任何东西也必须更大，因此它们不能成为更大的 first 元素，因此我们不需要搜索他们。因此，中间元素是最后一个可能的位置。

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.

请注意，在每次迭代中，我们会至少考虑其余元素的一半。如果执行顶部分支，则[low，（low + high）/ 2]范围内的元素都将被丢弃，从而使我们损失底价（（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.

如果执行底部分支，则在[（低+高）/ 2 + 1，高]全部丢弃。这使我们失去了上限-下限（低+高）/ 2 +1> =高-（低+高）/ 2 =（高-低）/ 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屋！