从有序的数组中查找某个值

分类: IT文章 • 2023-11-06 13:47:48

问题：

给定长度为N的单调不下降数列，求满足ai>=k的最小i。

输入：

5 3

2 3 3 5 6

输出：

#include<stdio.h>
int main()
{
    int n,k;
    int a[100];
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int st=-1,en=n;
    while(en-st>1)
    {
        int mid=(en+st)/2;
        if(a[mid]>=k)
            en=mid;
        else
            st=mid;
    }
    printf("%d
",en);
}

View Code

这样是不是很麻烦呢？现在附上STL的lower_bound 函数的实现；

首先简单理解下lower_bound 的基本应用：

头文件：#include<algorithm>

#include <algorithm>//必须包含的头文件
#include <stdio.h>
using namespace std;
int main()
{
    int n,a[100],m;
    int left,right,i;
    scanf("%d",&n);//设初始数组内元素有n个
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);//插入的数为m
     left = upper_bound(a,a+n,m)-a;//按从小到大，m最多能插入数组a的哪个位置
     right = lower_bound(a,a+n,m)-a;//按从小到大，m最少能插入数组a的哪个位置
 
     printf("m最多能插入数组a的%d
",left);
     for(i=0;i<left;i++)
        printf("%d ",a[i]);
    printf("%d ",m);
    for(i=left;i<n;i++)
        printf("%d ",a[i]);
 
    printf("
");
 
    printf("m最少能插入数组a的%d
",right);
    for(i=0;i<right;i++)
        printf("%d ",a[i]);
    printf("%d ",m);
    for(i=right;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}

View Code

函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置

举例如下：

一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

则

pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。

pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。

pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。

所以，要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~

返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置

从有序的数组中查找某个值

相关推荐