C++021-C++二分查找
在线练习：
总结
本系列为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; }
