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。
代码语言：javascript复制#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
代码语言：javascript复制#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
代码语言：javascript复制#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值为%dn",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 【分析】 和寻找第一个大于等于某数字方法比，增加一个条件，就是确定左边界必须和找的数字一样
代码语言：javascript复制#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值为%dn",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
代码语言：javascript复制#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值为%dn",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/
