发现在阵列大于所述目标的第一个元素 [英] Find the first element in an array that is greater than the target

问题描述

在一般的二进制搜索，我们正在寻找出现在数组中的值。 Iometimes，我们需要寻找的第一个元素比目标更高/更低。

in a general binary search, we are looking for a value which appears in the array. Iometimes, we need looking for the first element that is greater/less than a target.

下面是一个二进制搜索code与我的丑陋的解决方案：

Here is a binary search code with my ugly solution:

  // assuming all element is greater than 0
  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] < ) 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?

谢谢！

推荐答案

在思考这个问题的一个特别优雅的方式是考虑做一个二进制搜索在阵列，其中阵列已通过应用改良的转换后的版本功能

A particularly elegant 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;
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 left 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.

请注意，每次我们落了至少一半的剩余的元素从考虑迭代。如果顶部分支执行时，则在区间[低（低+高）/ 2]的元素都被丢弃，导致我们失去楼（（低+高）/ 2） - 低+ 1> =（低+高）/ 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

因此​​，我们计算中旬=（0 + 6）/ 2 = 3，所以我们考察在位置3的元素，它的值为1。由于1> 0，我们设置高= =中旬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

我们计算中旬=（0 + 3）/ 2 = 1，所以我们考察要素1.由于本有价值0℃= 0，我们设置中期=低+ 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

现在，我们计算中间=（2 + 3）/ 2 = 2。在索引2中的元素是1，并且由于1格; 0，我们设定H =中等= 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屋！