C++021-C++二分查找

在线练习：
http://noi.openjudge.cn/
https://www.luogu.com.cn/

总结

本系列为C++学习系列，会介绍C++基础语法，基础算法与数据结构的相关内容。本文为C++中的二分查找案例，包括相关案例练习。

二分查找

本文的目标在于:

1、了解二分法的基本概念
2、掌握二分查找的基本框架
3、了解二分查找的简单题型

二分查找思路

该方法是建立在有序的前提下的，基本思路就是：

先找到那个有序序列的中间元素mid，然后拿它和要找的元素K进行比较，就可以初步判断K所在范围。既然查找范围已确定，自然该范围之外的元素就可以不用再查找了。接下来还会按照上面的步骤反复查找下去。

因为二分查找每一次查找都可以缩减掉一半的查找范围，由此可以知道二分查找法的时间复杂度是:log2​(N)。
举个例子来解释该时间复杂度：

若这里一共有2^32个元素，那么我在最坏的情况下也只需要32次就可以找到我想找的元素；而顺序查找法最坏的情况下，却需要查找 4,294,967,296‬ 次！！！

二分查找模板

在有序数组中查找某个数，找到返回数的下标，不存在重复的值，没有返回-1。

#include<iostream>
using namespace std;
// 三个参数分别是整个数组，数组的长度，查找值
int binary_search1(int a[],int n,int key)
{
    int low=1;// 左边界从1开始
    int high=n; //右边界从n开始
    while(low<=high) //low 到highshi 查找范围
    {
        int mid=low+(high-low)/2; //中间下标
        if(key==a[mid]) return mid;
        else if(key < a[mid]) high=mid-1;//mid-1为右边界
        else low=mid+1; // mid+1是左边界
    }
    return -1;//都不满足
}
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列
    int sz = sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数
    int index=binary_search1(arr,sz,7);
    if(index >=0)
    {
        cout<<index;
    }
    return 0;
}

题目描述-查找第一个大于k的位置

【描述】从一个有序的整数序列中查找第一个大于整数k的数，如果存在输出出现位置，否则输出-1。序列有重复元素，并且单调递增。
【输入】
两行，
第一行一个整数n表示n数字，k表示k的值;
【输出】
第一个大于整数k的数的位置
【样例输入】
10 8
1 2 3 4 5 6 7 8 9 10
【样例输出】
9

#include<iostream>
#include<stdio.h>
using namespace std;
// 三个参数分别是整个数组，数组的长度，查找值
int binary_search1(int a[],int n,int key)
{
    int low=1;// 左边界从1开始
    int high=n; //右边界从n开始
    while(low<=high) //low 到high 查找范围
    {
        int mid=low+(high-low)/2; //中间下标
        if(key<a[mid]) high=mid-1; //当key小于中间值，把查找范围最大值左移
        else low=mid+1; // key大于等于中间值 查找范围右移最小值
        printf("low -- %d ,mid--%d,high-- %d, \n",low,mid,high);
    }
    if(low<=n) return low;
    //判断左边界是否越界
    else return -1;//都不满足
}
int main()
{
    int s[105],n,m,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    int index=binary_search1(s,n,m);
    cout<<index;
    return 0;
}

题目描述：查找第一个大于等于k的位置

【描述】
从一个有序的整数序列中查找第一个大于或等于整数k的数，如果存在输出出现位置，否则输出-1。序列有重复元素，并且单调递增。
【输入】
两行，
第一行一个整数n表示n数字，k表示k的值;
【输出】
第一个大于等于整数k的数的位置
【样例输入】
10 6
1 2 3 4 5 6 6 9 9 9
【样例输出】
6

#include<iostream>
#include<stdio.h>
using namespace std;
// 三个参数分别是整个数组，数组的长度，查找值
int binary_search1(int a[],int n,int key)
{
    int low=1;// 左边界从1开始
    int high=n; //右边界从n开始
    while(low<=high) //low 到high 查找范围
    {
        int mid=low+(high-low)/2; //中间下标
        if(key<=a[mid]) high=mid-1; //当key小于等于中间值，把查找范围最大值左移 相等时，high会左移到错位
        else low=mid+1; // key大于等于中间值 查找范围右移最小值
        printf("low -- %d ,mid--%d,high-- %d, mid值为%d\n",low,mid,high,a[mid]);
    }
    if(low<=n) return low;
    //判断左边界是否越界
    else return -1;//都不满足
}
int main()
{
    int s[105],n,m,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    int index=binary_search1(s,n,m);
    cout<<index;
    return 0;
}

题目描述：查找特点元素第一次出现的位置

【描述】从一个有序的整数序列中查找整数k，如果存在输出第一次出现位置，否则输出-1。序列有重复元素，并且单调递增。
【输入】第一行是两个整数n和m; n为序列中整数的个数,m为询问次数;第二行是n个递增的整数;第三行是m个整数，为查找的目标;
【输出】m行;m个查询结果。

【样例输入】
10 3
1 2 3 3 3 4 4 6 6 6
3 5 6
【样例输出】
3
-1
8
【分析】
和寻找第一个大于等于某数字方法比，增加一个条件，就是确定左边界必须和找的数字一样

#include<iostream>
#include<stdio.h>
using namespace std;
// 三个参数分别是整个数组，数组的长度，查找值
int binary_search1(int a[],int n,int key)
{
    int low=1;// 左边界从1开始
    int high=n; //右边界从n开始
    while(low<=high) //low 到high 查找范围
    {
        int mid=low+(high-low)/2; //中间下标
        if(key<=a[mid]) high=mid-1; //当key小于等于中间值，把查找范围最大值左移 相等时，high会左移到错位
        else low=mid+1; // key大于等于中间值 查找范围右移最小值
        printf("low -- %d ,mid--%d,high-- %d, mid值为%d\n",low,mid,high,a[mid]);
    }
    if(low<=n && a[low]==key) return low; //左侧不越界并且左侧等于key
    else return -1;//都不满足
}
int main()
{
    int s[105],n,m,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=m;i++)
    {
        cin>>b;
        cout<<binary_search1(s,n,b)<<endl;
    }
    return 0;
}

题目描述：查找特点元素最后一次出现的位置

【描述】从一个有序的整数序列中查找整数k，如果存在输出最后一次出现位置，否则输出-1。序列有重复元素，并且单调递增。
【输入】第一行是两个整数n和m; n为序列中整数的个数，m为询问次数;第二行是n个递增的整数;第三行是m个整数，为查找的目标;
【输出】m行; m个查询结果。

【样例输入】
10 3
1 2 3 3 3 4 4 6 6 6
3 5 6
【样例输出】
5
-1
10

#include<iostream>
#include<stdio.h>
using namespace std;
// 三个参数分别是整个数组，数组的长度，查找值
int binary_search1(int a[],int n,int key)
{
    int low=1;// 左边界从1开始
    int high=n; //右边界从n开始
    while(low<=high) //low 到high 查找范围
    {
        int mid=low+(high-low)/2; //中间下标
        if(key<a[mid]) high=mid-1; //当key小于等于中间值，把查找范围最大值左移
        else low=mid+1; // key大于等于中间值 查找范围右移最小值
        printf("low -- %d ,mid--%d,high-- %d, mid值为%d\n",low,mid,high,a[mid]);
    }
    if(low-1>1 && a[low-1]==key) return low-1; //找到low的位置向前一个
    else return -1;//都不满足
}
int main()
{
    int s[105],n,m,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=m;i++)
    {
        cin>>b;
        cout<<binary_search1(s,n,b)<<endl;
    }
    return 0;
}

在线练习：

http://noi.openjudge.cn/