|
目录
什么是二分
举例
代码模型
例题
题目描述
输入格式
输出格式
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;
}
|