博客

二分查找是一种很简单且常用的算法，常用于线性查找，在10000个数里面查找一个数，用循环查找最坏的情况最坏的情况是10000，但用二分就可以降到logn的时间代价

但是二分算法有一个缺点，也就是它运行的原理：所查找的序列必须是有序的。所以二分查找法不适用于最长不下降子序列的解决。

这个时候就要用到upper_bound函数和lower_bound函数来解决。

二分查找分为七种情况。

一：最朴素的二分查找，查找数num.

#include<bits/stdc++.h>
using namespace std;

int x,n,a[105];
bool flag=false;

void f(int l,int r){
	int mid=(l+r)/2;
	if(l>r)return ;
	if(a[mid]==x){
		flag=true;
		return ;
	}
	if(a[mid]<x)f(l,mid-1);
	if(a[mid]>x)f(mid+1,r);
	return ;
} 

int main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
	} 
	sort(a+1,a+n+1,greater<int>());//防止缺德、毒瘤数据 
	f(1,n);
	if(flag)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0; 
}

原理：大了就在左边搜，等于就直接结束，小了往右边搜。

上面给出的是递归代码，以下介绍的六种方法都可以用递归解决。

二：查找第一个与数num相等的值得位置。

核心代码:

int left = 0;
int right = n - 1;
while (left <= right) { // 这里是 <=
int mid = (left + right) >>1;
if (a[mid] >= key) {
right = mid - 1;
}else {
left = mid + 1;
} }
if (left < n && a[left] == key) {
return left;
} 
return -1;//不一定有相等的

三：最后一个与数num相等的数。

int left = 0;
int right = n - 1;
while (left <= right) { // 这里是 <=
int mid = (left + right) >>1;
if (a[mid] <= key) {
left = mid + 1;
}
else {
right = mid - 1;
} }
if (right >= 0 && a[right] == key) {
return right; }
return -1;

四：最后一个小于等于num的数

int left = 0;
int right = n - 1;
while (left <= right) {// 这里是 <=
int mid = (left + right) >>1;
if (a[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1; } }
return right;

五：最后一个小于num的数

int left = 0;
int right = n - 1;
while (left <= right) { // 这里是 <=
int mid = (left + right) >>1;
if (a[mid] >= key) {
right = mid - 1;
}
else {
left = mid + 1;
} }
return right;

六：第一个大于等于num的数

int left = 0;
int right = n - 1;
while (left <= right) { // 这里是 <=
int mid = (left + right) >>1;
if (a[mid] >= key) {
right = mid - 1; }
else {
left = mid + 1;
} }
return left;

七：第一个大于num的数

int left = 0;
int right = n - 1;
while (left <= right) { // 这里是 <=
int mid = (left + right) >>1;
if (a[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
} }
return left;

总体程序：

#include<cstdio>
#include<iostream>
using namespace std;
int a[1001], n;
// 查找第一个相等的元素
int findFirstEqual(int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] >= key) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	if (left < n && a[left] == key) {
		return left;
	}
	return -1;
}

// 查找最后一个相等的元素
int findLastEqual( int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] <= key) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	if (right >= 0 && a[right] == key) {
		return right;
	}
	return -1;
}
// 查找最后一个等于或者小于key的元素
int findLastEqualSmaller( int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] > key) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return right;
}
// 查找最后一个小于key的元素
int findLastSmaller(int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] >= key) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return right;
}
// 查找第一个等于或者大于key的元素
int findFirstEqualLarger(int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] >= key) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return left;
}
// 查找第一个大于key的元素
int findFirstLarger(int key) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {// 这里是 <=
		int mid = (left + right) / 2;
		if (a[mid] > key) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return left;
}
int main() {
	scanf("%d", &n);//n表示输入的数字个数
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);//输入n个数
	}
	//注意：除了第一个 findFirstEqual 和第2个findLastEqual 在找不到时输出-1，其他函数默认肯定可以找到 
	printf("First Equal           : %2d \n", findFirstEqual(5));
	printf("Last Equal            : %2d \n", findLastEqual(5));
	printf("Last Equal or Smaller : %2d \n", findLastEqualSmaller(5));
	printf("Last Smaller          : %2d \n", findLastSmaller(5));
	printf("First Equal or Larger : %2d \n", findFirstEqualLarger(5));
	printf("First Larger          : %2d \n", findFirstLarger(5));
	
	return 0;
}


/*
样例输入： 
17
1 2 2 5 5 5 5 5 5 5 5 5 5 6 6 7 9

样例输出：
First Equal           :  3
Last Equal            : 12
Last Equal or Smaller : 12
Last Smaller          :  2
First Equal or Larger :  3
First Larger          : 13

样例输入： 
10
1 2 2 5 5 5 6 6 7 9 
样例输出：
First Equal           :  3
Last Equal            :  5
Last Equal or Smaller :  5
Last Smaller          :  2 
First Equal or Larger :  3
First Larger          :  6

*/

总结：

二分查找法的算法思想是分治，并且该查找算法么查找一段区间就能“扔掉”一半，所以算法时间复杂度是o(logn)的。

以情况情况七种利用的是二分查找法，推广之后叫做二分法，也就是：规定一个中间值，如果答案和中间值（mid）的关系满足答案在左边，就抛弃右边所有情况，反之抛弃左边的所有情况。

向大家推荐两道题目：c++一本通

1241：二分法求函数的零点

1238：一元三次方程求解

有兴趣的读者可以继续推广，了解分治算法，

题库