分享内容

1. 二分查找的原理
2. 实现二分查找
3. STL二分查找函数

理论常识：常用操作系统简介(二)

UNIX:一个强大的多用户、多任务操作系统,支持多种处理器架构,具有强大的可移植性和良好的用户界面,常用于工程应用和科学计算。
Linux:一种开源的类UNIX操作系统。其源代码可以自由查看、修改和分发。Linux操作系统则具有广泛的兼容性,可以运行在多种不同的硬件平台上。Linux在服务器、云计算、物联网等领域的应用越来越广泛。UNIX和Linux在操作系统领域各有特色。UNIX闭源但稳定,Linux开源且兼容性强。

二分查找

猜数游戏

电脑随机生成一个1到100的整数。你可以进行多次猜测。每次猜测,你需要输入一个数字,
电脑给出“猜中了”、“大了”、“小了”这样的提示。
策略1:顺序查找从1开始猜测,然后猜2 …
·运气好的时候(随机数是1),一次猜中。
·运气不好的话(随机数是100),要猜100次。
最后猜100。
策略2:二分查找
·先猜测1和100中间的数字50。
·如果运气不错,刚好就是50,那么只需猜一次。
·如果50太小了,则范围缩到51到100。
·如果50太大了,则范围缩到1到49。
剩下49个数字,继续猜中间的数字。

100→50→25→12→6→3→1

最多只需要7次就可以找到答案。

二分查找的概念

● 二分查找(Binary search)也称折半查找
● 用于在有序数组中查找特定元素的位置
● 基本思想是将查找区间一分为二,然后根据目标值与区间中间元素的大小关系,决定下一步是在左区间还是右区间继续查找。
● 通过逐步减半提高了查找效率,是一种高效的查找算法
● 二分查找的前提条件:数据必须是有序的

二分查找的原理

二分查找的突现

int binSearch(int x) {//假设数组a[]和变量n都是全局变量
	int left = 1, right = n;
	while (left <= right) {
		int mid = (left + right)/2;// 中间位置
		if (a[mid] == x)
			return mid;// 刚好找到需要的数字
		else if (a[mid] > x)
			right =mid- 1;// 取区间的左一半
		else
			left =mid + 1;// 取区间的右一半
	}
	return -1;// 最后没有找到
}	

时间复杂度为O(logn),空间复杂度为O(1)

递归二分查拌

我们也可以用递归方式来实现二分查找
我们将搜索区间[left,right]对应的问题记为f(left,right)。

1. 如果区间为空(left>right),没找到,递归结束。
2. 计算中点mid。
3. 如果a[mid] == x,找到了,递归结束。
4. 如果a[mid]<x,则继续二分查找右区间,即递归求解f(mid+1,right)。
5. 如果a[mid]>x,则继续二分查找左区间,即递归求解f(left,mid-1)。
   二分查找的递归过程是基于问题规模的缩小,而不是问题的分解。

int binSearch(int x, int left, int right) {
	if (left > right)
	return -1;//递归出口1
}
int mid = (left + right) /2;

if ( x == a [mid] )
	return mid;//递归出口2
else if ( x < a[mid])
	return binSearch(x, left, mid-1);//递归查找左半区间
else
	return binSearch (x, mid+1, right);//递归查找右半区间
}
时间复杂度为O(logn),空间复杂度为O(logn)

二分查找-小结

● 二分查找的前提条件是数据必须是有序的
● 二分查找的时间复杂度为O(logn),是一种效率较高的查找(搜索)方法
● 如果用递归实现二分查找,需要额外的栈空间,空间复杂度一般是O(logn)
● 二分查找有多种正确的实现方式,需要处理好边界和循环判断等细节,避免写出死循环

【注意】以上二分查找函数仅适用要查找的数在数列中最多只有一个的情况。如果有多个相同值存在,找到的位置是其中一个值的位置。后面(学以致用部分)单独讨论左右端点问题。

STL二分查找函数

STL中提供了三个主要的二分查找函数:
· binary_search:判断指定值是否存在于排序好的序列中
· lower_bound:二分查找排序好的序列中第一个>=指定值的元素
· upper_bound:二分查找排序好的序列中第一个>指定值的元素

● 用到头文件algorithm:#include
● 在使用之前,必须确保序列是已排序的。
● 如果未排序,函数调用的返回结果不可靠。

binary_search函数

● 一般使用方法:判断是否存在
bool found = binary_search (a+start, a+end+1, value) ;//注意前2个参数和查找范围的对应关系!

在已排序数组a的a[start]~a[end]范围内查找值value,找到返回true,否则返回false。

【代码示例】

if (binary_search (a+start, a+end+1, value) )
	cout << "元素" << value << "存在于数组中” << endl;
else
	cout << "元素" << value << "不存在于数组中” << endl;

【再次强调】如果数组未排序,函数调用的返回结果不可靠。

lower_bound函数

●一般使用方法:

二分查找第一个>=指定值的元素

int id = lower_bound (a+start, atend+1, value) - a;

lower_bound 返回值(地址)减去数组首地址,就是实际下标位置id。
1.如果所有值都<value,没找到,此时id=end+1(超出查找范围)。
2. 否则,找到了,但是分几种情况:
①如果数组中仅包含一个value,则id就是value所在的位置下标。
② 如果容器包含多个value,则id就是第一个value的位置下标。
例如,在{1,2,3,4,4,5}中查找>=4的值,得到的是下标3位置上的4。
③如果容器不包含value,则id就是第一个>value的值的位置下标。
【代码示例】使用lower_bound在a[start]~a[end]间查找第一个>=value的元素

int id = lower_bound (a+start, a+end+1, value) - a;
if(id>end)//没找到满足条件的(全部都<value)
	cout << "所有元素都小于” << value << endl;
else if(a[id] == value)// 找到第一个等于的
	cout << "元素” << value << "的位置是” << id << endl;
else // 找到第一个大于的
	cout << "第一个大于" << value << "的位置是" << id << endl;

upper_bound函数

● 一般使用方法:二分查找第一个>指定值的元素

int id = upper_bound (a+start, atend+1, value) - a;

upper_bound 返回值(地址)减去数组首地址,就是实际下标位置id。

1. 如果所有值都 <= value,没找到,此时id=end+1(超出查找范围)。
2. 否则,找到了,则id是第一个>value的值的位置下标。

int id = upper_bound (a+start, a+end+1, value) - a;
if(id >end)// 全部都 <= value
	cout << "所有元素都小于等于" << value << endl;
else // 找到第一个大于的
	cout << "第一个大于" << value << "的位置是” << id << endl;

· STL提供的二分查找函数已经实现了二分查找算法,无需自己实现。
· STL实现的二分查找算法通常会利用现代编译器的优化,比如循环展开、指令重
排等,执行效率更高。
· 使用STL提供的二分查找函数的前提是数据已经排好序。
· 注意函数调用后对不同情况下返回值的检查。

多使用,多练习,熟能生巧

简单二分查拌

请在一个有序递增数列中(不存在相同元素),采用二分查找,找出值x的位置,如果x在数列中不存在,请输出-1!
【输入】第一行,一个整数n,代表数列元素个数(n <= 100)。
第二行,n个整数,代表数组的n个递增元素(1 <= 数组元素值 <= 10^8)
第三行,一个整数x,代表要查找的数(0 <= x <= 10^8)
【输出】x在数列中的位置,位置从1开始编号;没找到,输出-1。
【输入用例】
10
1 3 5 7 9 11 13 15 17 19

3

【输出用例】2
练习为目的,掌握二分查找原理,以及STL二分查找函数的使用。

自定义二分查找函数

补充完整算法流程

1. 定义left,right指针,分别指向数组的最左最右。
2. 计算中间点mid:mid=(left+right)/2
3. 分三种情况讨论:
   · arr[mid] == x说明正好找到,返回mid的值;
   · arr[mid]>x说明[mid,right]这段区间都是大于x的,因此舍去右边区间,在左边[left,mid-1]的区间继续查找,即让right=mid-1;
   · arr[mid]<x说明[left,mid]这段区间的值都是小于x的,因此舍去左边区间,在右边[mid+1,right] 区间继续查找,即让left=mid+1;
4. 重复2、3,直到left与right错开(即left>right)时,说明整个区间都没有这个数,返回-1。

实现二分查找函数

int a[110];
int n;

int binSearch(int x) {
	int left = 1, right = n;
	while (left <= right) {
		int mid = (left + right)/ 2;// 中间位置
		if (a[mid] == x)
			return mid;// 刚好找到需要的数字
		else if (a[mid] > x)
			right = mid- 1;// 下次查找区间的前一半
		else
			left =mid+ 1;// 下次查找区间的后一半
	}
	return -1;// 最后没有找到

完整代码

#include <iostream>
using namespace std;
int a[110];
int n;

// 在数组a[]中二分查找x的位置
// 如果找到x,则返回x在数组a中的下标,否则返回-1
int binSearch(int x) {
	int left = 1, right = n;
	while (left <= right) {
		int mid=(left + right)/2;//中间数的位置
		if (a[mid] == x)
			return mid;//刚好找到需要的数字
		else if (a[mid] > x)
			right=mid-1;//取区间的前一半
		else
			left = mid + 1;// 取区间的后一半
	}
	return-1;//最后没有找到
}
int main(){
	int x;//要查找的值
	cin >> n;
	for(int i=1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> x;
	cout << binSearch (x) ;
	return 0;
}

【注意】

1. 数组a和变量n定义为全局变量的情况下,可直接使用,无需作为函数参数传入。
2. 输入的数从下标1开始存放,所以二分查找的初始范围是[1,n]。
   

STL二分查找函数

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[110] ;
int n;

int main(){
	int x;// 要查找的值
	cin >> n;
	for(int i=1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> x;
	// 先用1ower bound查找第一个>=x的值,后筛选出=x的情况
	int id = lower bound (a+1, a+n+1, x) - a;
	if(id>n)//没找到(全部都<x)
		cout << -1;
	else if (a[id] == x) // f/ == x
		cout << id ;
	else//只找到大于x的值,所以还是没找到x
		cout << -1;
	return 0;
}

二分查找右端点(右边界)

请在一个有序不递减的数列中(数列中有相等的值),采用二分查找,找到值x的右端点(最后出现的位置),如果不存在x请输出-1。
【输入】第一行,一个整数n,代表数列元素个数(n <= 100)
第二行,n个整数,代表数组的n个递增元素(1 <= 数组元素值 <= 10^8)
第三行,一个整数x,代表要查找的数(0 <= x <= 10^8)
【输出】x在数列中最后出现的位置,位置从1开始编号;没找到,输出-1。
【输入样例】
9
3 3 3 4 9 11 13 15 17

3

【输出样例】3

找右端点分析

【输入样例】
9
3 3 3 4 9 11 13 15 17
3
【输出用例】
3------------>最后一个3出现在位置3

试着用上一题的二分查找的程序,看看能不能得到正确的右端点?

自定义二分函数法得到输出为2------>得到的是多个x中的任一个的位置

STL lower_bound法得到输出为1------->升序情况下,lower_bound能得到×的左端点

都不是正确的右端点位置

思路

思路1:一次二分查找+部分遍历

· 先二分查找x,如果不能查找到,返回-1;
· 如果可以查找到,就从该下标开始向右遍历数组,返回最右边的x的下标。
· 时间复杂度O(logn+n),取最高项,时间复杂度为O(n)。

思路2:直接二分查找区间右端点

· 步骤 ??
· 时间复杂度O(logn)

思路1可基于上一练习的代码自行实现

实现函数二分查找右端点

int findRight (int x) {
	int left = 1, right = n ;
	while (left <= right) {
		int mid = (left + right) / 2;
		if ( x < a[mid] )
			right = mid - 1;
		else//(x>=a[mid])继续向右找
			left = mid + 1;
		}
		if(a[left-1] == x)//判断Left-1(或者Right)的值是否等于x
			return left-1;
		else
			return -1;
}

如果a[left-1] == x说明找到了,且left-1就是x的右端点,否则说明x没有出现在整个队列中

完整代码

#include <iostream>
using namespace std;
int a[110];
int n,x;

//查找右端点:本质是找Left,即第一个>x的数的位置
// 要判断Left-1(或者Right)的值是否等于x
int findRight (int x) {
	int left = 1, right = n ;
	while (left <= right) {
		int mid = (left + right) / 2;
		if ( x < a[mid] )
			right = mid - 1;
		else // ( x > a[mid] )继续向右找
			left = mid + 1;
	}
	// 判断Left-1(或者Right)的值是否等于x
	if (a[left-1] == x)
		return left-1;
	else
		return -1;
}
int main() {
	cin >> n;
	for(int i=1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> x;
	cout << findRight (x);
	return 0;
}

【注意】
· 二分查找有很多种正确的写法,并不局限于本例题给出的方式。
· 二分时选择不同的边界,代码相应也不同。

#include <iostream>
#include <algorithm>
using namespace std;
int a[110] ;
int n,x;

int main(){
	cin >> n;
	for(int i=1; i <= n; i++) {
	cin >> a[i];
	}
	cin >> x;
/*
用STL upper bound函数先找到第一个>指定值的位置
再查看前一个值是否 == 指定值,等于,则找到了这个值的右端点
否则没找到,返回-1
*/
	int id = upper bound (a+1, a+n+1, x) - a;
	if (a[id-1] == x)
		cout << id -1;
	else
		cout << -1;
	return 0;
}

本次课程的知识点

1. 二分查找的原理、前提条件
2. 二分查找唯一值(递归方式、非递归方式)
3. STL二分查找函数的功能和用法
4. 二分查找右端点
5. 二分查找左端点
   
   

二分查找左端点(左边界)

请在一个有序不递减的数列中(数列中有相等的值),采用二分查找,找到值x的左端点(第一次出现的位置),如果不存在x请输出-1。
【输入】第一行,一个整数n,代表数列元素个数(n <= 100)
第二行,n个整数,代表数组的n个递增元素(1 <= 数组元素值 <= 10^8)
第三行,一个整数x,代表要查找的数(0 <= x <= 10^8)
【输出】x在数列中第一次出现的位置,位置从1开始编号;没找到,输出-1。
【输入样例1】
9
3 3 3 4 9 11 13 15 17
3

【输出样例1】1

【输入用例2】
10
1 3 5 7 9 11 13 15 17 19

-2

【输出用例2】-1

#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int n,x;

int main(){
	cin >> n;
	for(int i=1; i <= n; i++) {
	cin >> a[i];
	}
	cin >> x;
	// 先找第一个>=x的值的位置id
	int id = lower bound (a+1, a+n+1, x) - a;
	cout << id << endl;
	if(id>n ll a[id] != x)// 没找到,或者只找到>x的值
		cout << -1;
	else
		cout << id;
	return 0;
}

【注意】必须要测试找到和没找到两种情况
【挑战】试着自己实现二分查找左端点,有点难度!