目录

什么是二分

举例

代码模型

不足

改进代码

例题

题目描述

输入格式

输出格式

AC代码：

三分搜索

什么是二分

假设一维数组 data 已经按升序排列，二分查找算法根据当前需要查找的区间[left，right]定义一个中间位置 middle＝(left＋right)/2，将待查找值 x 与数组元素 data[middle]进行比较，有三种情况：
（1）x＝data[middle]，则找到了该元素；
（2）x＞data[middle]，由于数组是按升序排列的，待寻找的值要么不在数组中，要么只可能在右半区间[middle＋1，right]；
（3）x＜data[middle]，待寻找的值要么不在数组中，要么只可能在左半区间[left，middle－1]。由于每次查找都是在原区间的一半内进行，又称为折半查找，总的时间复杂度为 Ο(logn)。

举例

以一个具体的例子来说明二分查找的工作过程。设 data[10]＝{1，2，3，4，5，6，7，8，9，10}，待查找的值 x＝7，初始时，需要查找的区间为[left＝0，right＝9]，中间位置 middle＝(left＋right)/2＝(0＋9)/2＝4，由于 data[4]＝5＜x＝7，则应该在右半区间[left＝middle＋1＝5，right＝9]中继续查找，此时 middle＝(5＋9)/2＝7，而 data[7]＝8＞x＝7，应该继续在左半区间[left＝5，right＝middle－1＝6]中查找，之后 middle＝(5＋6)/2＝5，data[5]＝6＜x＝7，将查找区间更新为[left＝middle＋1＝6，right＝6]，最后 middle＝(6＋6)/2＝6，data[6]＝x＝7。

代码模型

int erfen(int data[], int n, int x)
{
int left = 0, right = n - 1;
while (left <= right) 
{
int middle = (left + right) / 2;
if (data[middle] == x) return middle;
if (data[middle] < x) left = middle + 1;
else right = middle - 1;
}
return -1;
}

不足

（1）使用 middle＝(left＋right)/2 的方式来获取中间值，如果 left＋right 接近其声明的数据类型的表示上限，则 left＋right 会溢出，从而导致错误，更为稳妥的方法是使用：middle＝left＋(right－left)/2，这样能最大程度的避免溢出。
（2）如果数组中包含多个相同的目标值，上述实现返回的序号并不一定是数组中第一个目标值的序号，比如极端的情况——数组中的所有元素值均相同，此时使用上述实现查找某个元素值时，要么不存在，要么返回的总是中间的固定位置。

改进代码

int erfen(int data[], int n, int x)
{
int left = -1, right = n, middle;
while ((left + 1) != right) 
{
middle = left + (right - left) / 2;
if (data[middle] < x) left = middle;
else right = middle;
}
if (right >= n || data[right] != x) right = -1;
return right;
}

例题

P2249

题目描述

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1。

输入格式

第一行 2 个整数 n和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

输出一行，m个整数，以空格隔开，表示答案。

AC代码：

#include<cstdio>
using namespace std;

int n,m,q,a[1000005];

int find(int x) //二分
{
	int l=1,r=n;
	while (l<r)
	{
		int mid=l+(r-l)/2;
		if (a[mid]>=x) r=mid;
		else l=mid+1;
	}
	
	if (a[l]==x) return l; //找都了就输出他的位置 
	else return -1; // 没找到输出-1 
}

int main()
{
	scanf("%d %d",&n,&m);
	
	for (int i=1 ; i<=n ; i++)
	    scanf("%d",&a[i]);
	
	for (int i=1 ; i<=m ; i++)
	{
		scanf("%d",&q);
		int ans=find(q); //看看查找的结果 
		printf("%d ",ans); //输出 
	}
	
	return 0;
}

三分搜索

在某些情形下，根据题目所得到的函数可能在定义域内并不是一个单调递增（或递减）函数，而是一个单峰函数（例如抛物线函数），此时应用二分搜索无法确定函数的极值，而应用三分搜索则能够在 O(logn)的时间内得到解

三分搜索的思路是将变量的取值范围划分为三个不同的区间，根据函数值的大小关系，使用类似于二分查找的方法来不断缩小极值可能所处的变量范围。

假设函数 f(x)为单峰函数，自变量 x 的定义域为[left，right]，在定义域内有最大值。设 leftThird＝left＋(right－left)/3，rightThird＝right－(right－left)/3，则 f(leftThird)和 f(rightThird)的大小关系为以下三种之一：f(leftThird)＜f(rightThird)：表明最大值不可能在左区间[left，leftThird]，应该在右区间[rightThird，right]中寻找最大值，更新 left＝leftThird。

f(leftThird)＞f(rightThird)：表明最大值不可能在右区间[rightThird，right]，应该继续在左区间[left，
leftThird]中寻找最大值，更新 right＝rightThird。

f(leftThird)＝f(rightThird)：表明最大值落在区间[leftThird，rightThird]中，此种情况可以合并在前述的任意一种情况中。持续缩小区间的范围，直到 left 和 right 之间的差值小于指定的阈值，此时变量 left 所对应的函数值 f(left)即为最大值。如果要求最小值，只需在比较函数值大小时将比较操作反向或者更改区间的选择即可。