查找排序数组中第一个大于目标的元素-Java 学习之路

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

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

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

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

7 回答

70
一个特别优雅的思考这个问题的方法是考虑对数组的转换版本进行二进制搜索，其中数组已经通过应用函数进行了修改
```
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. */
```
要查看此算法是否正确，请考虑进行每次比较 . 如果我们找到一个's no greater than the target element, then it and everything below it can'可能匹配的元素，那么'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是 first 元素，它们需要搜索它们 . 因此，中间元素是它可能的最后一个可能的位置 .

请注意，在每次迭代时，我们至少会考虑剩余的一半元素 . 如果顶部分支执行，则[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 .

希望这可以帮助！
回复于 2024-04-30T19:56:31+08:00

如果数组已排序，则可以使用 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;

回复于 2024-04-30T19:56:31+08:00

以下递归方法如何：

public static int minElementGreaterThanOrEqualToKey(int A[], int key,
        int imin, int imax) {

    // Return -1 if the maximum value is less than the minimum or if the key
    // is great than the maximum
    if (imax < imin || key > A[imax])
        return -1;

    // Return the first element of the array if that element is greater than
    // or equal to the key.
    if (key < A[imin])
        return imin;

    // When the minimum and maximum values become equal, we have located the element. 
    if (imax == imin)
        return imax;

    else {
        // calculate midpoint to cut set in half, avoiding integer overflow
        int imid = imin + ((imax - imin) / 2);

        // if key is in upper subset, then recursively search in that subset
        if (A[imid] < key)
            return minElementGreaterThanOrEqualToKey(A, key, imid + 1, imax);

        // if key is in lower subset, then recursively search in that subset
        else
            return minElementGreaterThanOrEqualToKey(A, key, imin, imid);
    }
}

回复于 2024-04-30T19:56:31+08:00

我的以下实现使用条件 bottom <= top ，这与@templatetypedef的答案不同 .

int FirstElementGreaterThan(int n, const vector<int>& values) {
  int B = 0, T = values.size() - 1, M = 0;
  while (B <= T) { // B strictly increases, T strictly decreases
    M = B + (T - B) / 2;
    if (values[M] <= n) { // all values at or before M are not the target
      B = M + 1;
    } else {
      T = M - 1;// search for other elements before M
    }
  }
  return T + 1;
}

回复于 2024-04-30T19:56:31+08:00

这是 JAVA 中修改后的 binary search 代码，时间复杂度为 O(logn) ：

返回 index 要搜索的元素 if element is present
如果搜索的元素不在数组中，则
返回下一个更大元素的索引
如果搜索大于数组最大元素的元素，则
返回-1

public static int search(int arr[],int key) {
    int low=0,high=arr.length,mid=-1;
    boolean flag=false;

    while(low<high) {
        mid=(low+high)/2;
        if(arr[mid]==key) {
            flag=true;
            break;
        } else if(arr[mid]<key) {
            low=mid+1;
        } else {
            high=mid;
        }
    }
    if(flag) {
        return mid;
    }
    else {
        if(low>=arr.length)
            return -1;
        else
        return low;
        //high will give next smaller
    }
}

public static void main(String args[]) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    //int n=Integer.parseInt(br.readLine());
    int arr[]={12,15,54,221,712};
    int key=71;
    System.out.println(search(arr,key));
    br.close();
}

回复于 2024-04-30T19:56:31+08:00

9
经过多年的教学算法，我解决二进制搜索问题的方法是在元素上设置开始和结束，而不是在数组之外 . 通过这种方式，我可以感受到正在发生的事情，一切都在掌控之中，而不会对解决方案产生魔力 .

解决二进制搜索问题（以及许多其他基于循环的解决方案）的关键点是一组良好的不变量 . 选择正确的不变量可以解决问题 . 我花了很多年才掌握这个不变的概念，虽然我多年前在大学里学过它 .

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

总而言之，到目前为止，我们有：
```
int start = 0; 
int end = a.length - 1;
```
现在是不变的 . 我们现在拥有的数组是[start，end] . 到目前为止，我们还没有对这些元素做出任何假设 . 我们的目标是找到比目标更大的第一个元素 . 所以我们像这样选择 invariants ：

右边的任何元素都大于目标 . 开头左侧的任何元素都小于或等于目标 .

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

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

另外我们需要注意的是，当循环结束时，start将比结束时多一个 . 即start = end 1.所以我们可以说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在内的所有数组大小要容易得多 .

所以希望这澄清了这个问题和许多其他二进制搜索问题的解决方案 . 将此解决方案视为专业地理解和解决更多二进制搜索问题的一种方式，而不会摇晃算法是否适用于边缘情况 .
回复于 2024-04-30T19:56:31+08:00

kind = 0：完全匹配，kind = 1：只比x更重，kind = -1：只比x小;

如果未找到匹配，则返回-1 .

#include <iostream>
#include <algorithm>

using namespace std;


int g(int arr[], int l , int r, int x, int kind){
    switch(kind){
    case 0: // for exact match
        if(arr[l] == x) return l;
        else if(arr[r] == x) return r;
        else return -1;
        break;
    case 1: // for just greater than x
        if(arr[l]>=x) return l;
        else if(arr[r]>=x) return r;
        else return -1;
        break;
    case -1: // for just smaller than x
        if(arr[r]<=x) return r;
        else if(arr[l] <= x) return l;
        else return -1;
        break;
    default:
        cout <<"please give "kind" as 0, -1, 1 only" << ednl;
    }
}

int f(int arr[], int n, int l, int r, int x, int kind){
    if(l==r) return l;
    if(l>r) return -1;
    int m = l+(r-l)/2;
    while(m>l){
        if(arr[m] == x) return m;
        if(arr[m] > x) r = m;
        if(arr[m] < x) l = m;
        m = l+(r-l)/2;
    }
    int pos = g(arr, l, r, x, kind);
    return pos;
}

int main()
{
    int arr[] = {1,2,3,5,8,14, 22, 44, 55};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+n);
    int tcs;
    cin >> tcs;
    while(tcs--){
        int l = 0, r = n-1, x = 88, kind = -1; // you can modify these values
        cin >> x;
        int pos = f(arr, n, l, r, x, kind);
        // kind =0: exact match, kind=1: just grater than x, kind=-1: just smaller than x;
        cout <<"position"<< pos << " Value ";
        if(pos >= 0) cout << arr[pos];
        cout << endl;
    }
    return 0;
}

回复于 2024-04-30T19:56:31+08:00

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

7 回答

相关问题