文章目录

• C++021-C++二分查找
• • 总结
  • 二分查找
  • • 二分查找思路
    • 二分查找模板
    • • 题目描述-查找第一个大于k的位置
      • 题目描述：查找第一个大于等于k的位置
      • 题目描述：查找特点元素第一次出现的位置
      • 题目描述：查找特点元素最后一次出现的位置
  • 在线练习：

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

#include
#include
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(keyint 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<

#include
#include
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<

#include
#include
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; //左侧不越界并且左侧等于keyelse 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<

#include
#include
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(key1 && 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<