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/