STL中的二分查找——lower_bound 、upper_bound 、binary_search

时间：2021-06-06 10:43:08

STL中的二分查找函数

1、lower_bound函数

在一个非递减序列的前闭后开区间[first,last)中。进行二分查找查找某一元素val。函数lower_bound()返回大于或等于val的第一个元素位置（即满足条件a[i]>=val(first<=i<last)的最小的i的值），当区间的全部元素都小于val时，函数返回的i值为last（注意：此时i的值是越界的！！！！！

）。

比方：已知数组元素是a[10]={0,2,2,2,6,8,10,16,60,100}

当val=0时，函数lower_bound()返回值为0；

当val=1时。函数lower_bound()返回值为1。

当val=2时，函数lower_bound()返回值为1；

当val=3时。函数lower_bound()返回值为4；

当val=4时，函数lower_bound()返回值为4；

当val=5时，函数lower_bound()返回值为4；

当val=6时，函数lower_bound()返回值为4；

当val=7时。函数lower_bound()返回值为5。

当val=8时，函数lower_bound()返回值为5。

当val=9时，函数lower_bound()返回值为6；

当val=10时。函数lower_bound()返回值为6。

当val=11时，函数lower_bound()返回值为7；

当val=59时。函数lower_bound()返回值为8。

当val=60时。函数lower_bound()返回值为8；

当val=61时。函数lower_bound()返回值为9；

当val=100时。函数lower_bound()返回值为9；

当val=101时，函数lower_bound()返回值为10。

当val=150时。函数lower_bound()返回值为10。

当val=500时。函数lower_bound()返回值为10；

STL中函数lower_bound()的代码实现(first是终于要返回的位置)

int lower_bound(int *array, int size, int key)

{

    int first = 0, middle, half, len;

    len = size;

    while(len > 0)

    {

        half = len >> 1;

        middle = first + half;

        if(array[middle] < key)

        {

            first = middle +1;

            len = len - half -1;//在右边子序列中查找

        }

        else

            len = half;//在左边子序列（包括middle）中查找

    }

}

vector容器储存序列值时的执行程序：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <sstream>

#include <fstream>

#include <limits.h>

#define debug "output for debug\n"

#define pi (acos(-1.0))

#define eps (1e-4)

#define inf (1<<28)

#define sqr(x) (x) * (x)

#define mod 1e9+7

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

int main()

{

    int i,x,n,m;

    vector<int> a;

    printf("输入数组长度n(0<n<10000)：");

    scanf("%d",&n);

    printf("输入数组的n个元素：");

    for(i=0;i<n;i++)

    {

        scanf("%d",&x);

        a.push_back(x);

    }

    sort(a.begin(),a.end());//排序（非递减序列）

    printf("元素值a[i]/下标i：\n");

    for(i=0;i<n;i++)

        printf("%d/%d\n",a[i],i);

    printf("输入查找的元素m：");

    vector<int>::iterator it;

    while(scanf("%d",&m)!=EOF)

    {

        //vector容器储存序列值时的函数调用方式

        it=lower_bound(a.begin(),a.end(),m);//返回值是迭代器的值

        printf("返回位置对于的值：%d\n",*it);

        printf("输入查找的元素m：");

    }

    return 0;

}

数组储存序列值时的执行程序：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <sstream>

#include <fstream>

#include <limits.h>

#define debug "output for debug\n"

#define pi (acos(-1.0))

#define eps (1e-4)

#define inf (1<<28)

#define sqr(x) (x) * (x)

#define mod 1e9+7

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

int main()

{

    int i,j,k,n,m,first,last;

    int a[10000];

    printf("输入数组长度n(0<n<10000)：");

    scanf("%d",&n);

    printf("输入数组的n个元素：");

    for(i=0;i<n;i++)

        scanf("%d",&a[i]);

    sort(a,a+n);//排序（非递减序列）

    printf("元素值a[i]/下标i：\n");

    for(i=0;i<n;i++)

        printf("%d/%d\n",a[i],i);

    printf("输入区间[first,last)(first<=last<=n)：");

    while(scanf("%d%d",&first,&last)!=EOF)

    {

        printf("输入查找的元素m：");

        scanf("%d",&m);

        //数组储存序列值时的函数调用方式

        j=lower_bound(a+first,a+last,m)-a;

        printf("返回位置：%d\n",j);

        printf("输入区间[first,last)(first<=last<=n)：");

    }

    return 0;

}

2、upper_bound函数

在一个有序序列（升序或者降序）的区间中。进行二分查找某一元素val。函数upper_bound返回一个迭代器指向该区间中最后一个这个元素的下一个位置（简单的说就是返回可以将元素val插入区间的最后一个位置）。

升序排列的容器：

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值>key的第一个元素。

降序排列的容器：

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值<key的第一个元素。

STL中函数upper_bound()的代码实现(first是终于要返回的位置)

int upper_bound(int *array, int size, int key)

{

    int first = 0, len = size-1, half, middle;

    while(len > 0)

    {

        half = len >> 1;

        middle = first + half;

        if(array[middle] > key)//中位数大于key,在包括last的左半边序列中查找。

len = half;

        else

        {

            first = middle + 1;//中位数小于等于key,在右半边序列中查找。

            len = len - half - 1;

        }

    }

    return first;

}

数组储存序列值时的执行程序：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <sstream>

#include <fstream>

#include <limits.h>

#define debug "output for debug\n"

#define pi (acos(-1.0))

#define eps (1e-4)

#define inf (1<<28)

#define sqr(x) (x) * (x)

#define mod 1e9+7

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

int main()

{

    int i,j,k,n,m;

    int a[10000];

    printf("输入数组长度n(0<n<10000)：");

    scanf("%d",&n);

    printf("输入数组的n个元素：");

    for(i=0;i<n;i++)

        scanf("%d",&a[i]);

    sort(a,a+n);//排序（非递减序列）

    printf("元素值a[i]/下标i：\n");

    for(i=0;i<n;i++)

        printf("%d/%d\n",a[i],i);

    printf("输入查找的元素m：");

    while(scanf("%d",&m)!=EOF)

    {

        //数组储存序列值时的函数调用方式

        j=upper_bound(a,a+n,m)-a;

        printf("返回位置：%d\n",j);

        printf("输入查找的元素m：");

    }

    return 0;

}

3、binary_search函数

函数binary_search是在有序序列的[first,last)中寻找元素value，若存在就返回true，若不存在则返回false。

程序执行例如以下：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <sstream>

#include <fstream>

#include <limits.h>

#define debug "output for debug\n"

#define pi (acos(-1.0))

#define eps (1e-4)

#define inf (1<<28)

#define sqr(x) (x) * (x)

#define mod 1e9+7

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

int main()

{

    int i,j,k,n,m;

    int a[10000];

    printf("输入数组长度n(0<n<10000)：");

    scanf("%d",&n);

    printf("输入数组的n个元素：");

    for(i=0;i<n;i++)

        scanf("%d",&a[i]);

    sort(a,a+n);//排序（非递减序列）

    printf("元素值a[i]/下标i：\n");

    for(i=0;i<n;i++)

        printf("%d/%d\n",a[i],i);

    printf("输入查找的元素m：");

    while(scanf("%d",&m)!=EOF)

    {

        //数组储存序列值时的函数调用方式

        j=binary_search(a,a+n,m);//j=upper_bound(a,a+n,m)-a;

        printf("返回位置：%d\n",j);

        printf("输入查找的元素m：");

    }

    return 0;

}

相关文章