查找排序数组中第一个大于目标的元素

Question

在一般的二进制搜索中,我们正在寻找出现在数组中的值.但是,有时我们需要找到比目标更大或更小的第一个元素.

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

// 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  
    }
  }
}

这种问题有更优雅的解决方案吗？

Answer 1

一个特别优雅的思考这个问题的方法是考虑对数组的转换版本进行二进制搜索,其中数组已经通过应用函数进行了修改

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

现在,目标是找到该函数对值1的第一个位置.我们可以使用二进制搜索来执行此操作,如下所示:

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. */

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

请注意,在每次迭代时,我们至少会考虑剩余的一半元素.如果顶部分支执行,则[low,(low + high)/ 2]范围内的元素全部被丢弃,导致我们失去底线((低+高)/ 2) - 低+ 1> =(低+高)/ 2 - 低=(高 - 低)/ 2个元素.

如果底部分支执行,则[(低+高)/ 2 + 1,高]范围内的元素都被丢弃.这使我们失去了高楼层(低+高)/ 2 + 1> =高 - (低+高)/ 2 =(高 - 低)/ 2元素.

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

编辑:这是在数组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.我们现在有

0 0 1
L     H

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

0 0 1
    L H

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

希望这可以帮助!

Answer 2

std::upper_bound如果数组已排序,则可以使用(假设n是数组的大小a[]):

int* p = std::upper_bound( a, a + n, x );
if( p == a + n )
     std::cout << "No element greater";
else
     std::cout << "The first element greater is " << *p
               << " at position " << p - a;

Answer 3

经过多年的算法教学，我解决二分搜索问题的方法是在元素上设置开始和结束，而不是在数组之外。通过这种方式，我可以感觉到正在发生的事情并且一切都在控制之中，而不会对解决方案感到神奇。

解决二分搜索问题（以及许多其他基于循环的解决方案）的关键点是一组好的不变量。选择正确的不变量使问题的解决变得轻而易举。我花了很多年才掌握不变性的概念，尽管我多年前在大学里第一次学会了它。

即使您想通过在数组外选择开始或结束来解决二分搜索问题，您仍然可以使用适当的不变量来实现它。话虽如此，我的选择如上所述，始终在数组的第一个元素上设置开始并在数组的最后一个元素上结束。

总而言之，到目前为止，我们有：

int start = 0; 
int end = a.length - 1; 

现在是不变量。我们现在拥有的数组是 [start, end]。我们对元素一无所知。它们都可能大于目标，或者都可能更小，或者一些更小，一些更大。所以到目前为止我们不能对元素做出任何假设。我们的目标是找到第一个大于目标的元素。所以我们选择这样的不变量：

end 右侧的任何元素都大于目标。
起点左侧的任何元素都小于或等于目标。

我们可以很容易地看到我们的不变量在开始时是正确的（即在进入任何循环之前）。开始左侧的所有元素（基本上没有元素）都小于或等于目标，结尾的推理相同。

有了这个不变式，当循环结束时，结尾之后的第一个元素将是答案（还记得结尾的右侧都大于目标的不变式吗？）。所以answer = end + 1。

另外我们需要注意的是，当循环结束时，start 会比 end 多一个。即 start = end + 1。所以等效地我们可以说 start 也是答案（不变的是 start 左边的任何东西都小于或等于目标，所以 start 本身是第一个大于目标的元素）。

所以一切都说了，这里是代码。你应该对这段代码的每一行都感到舒服，你应该感觉不到任何魔法。如果不是，请评论有什么歧义，我会很乐意回答。

public static int find(int a[], int target) {
    int st = 0; 
    int end = a.length - 1; 
    while(st <= end) {
        int mid = (st + end) / 2;   // or elegant way of st + (end - st) / 2; 
        if (a[mid] <= target) {
            st = mid + 1; 
        } else { // mid > target
            end = mid - 1; 
        }
    }
    return st; // or return end + 1
}

关于这种解决二分搜索问题的方法的一些额外说明：

这种类型的解决方案总是将子数组的大小至少缩小 1。这在代码中很明显。新的开始或结束是 +1 或 -1 中间。我更喜欢这种方法，而不是在两侧或一侧都包含中频，然后再解释为什么算法是正确的。通过这种方式，它更切实，更无错误。

while 循环的条件是st <= end。不是st < end。这意味着进入 while 循环的最小大小是大小为 1 的数组。这完全符合我们的预期。在解决二分查找问题的其他方法中，有时最小的数组是大小为 2 的数组（如果 st < end），老实说，我发现总是处理所有数组大小（包括大小 1）要容易得多。

所以希望这能澄清这个问题和许多其他二进制搜索问题的解决方案。将此解决方案视为一种专业理解和解决更多二分搜索问题的方法，而无需担心该算法是否适用于边缘情况。