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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

这是我的丑陋，不完整的解决方案：

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

对于这种问题是否有更优雅的解决方案？

回答：

解决此问题的一种方法是考虑对数组的转换版本执行二进制搜索，其中已通过应用函数修改了数组

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]范围内的元素都将被丢弃，从而使我们失去地板（（low + high）/ 2）-low +1> =（low +高）/ 2-低=（高-低）/ 2个元素。

如果执行底部分支，则将丢弃[（low + high）/ 2 +1，high]范围内的元素。这使我们损失了高-底（低+高）/ 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的元素处。

希望这可以帮助！

以上是 在排序数组中找到大于目标的第一个元素 的全部内容， 来源链接： utcz.com/qa/418515.html

回到顶部