脚本宝典收集整理的这篇文章主要介绍了二分查找(包括查找元素是第一次和最后出现的位置),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
这篇文章用于复习
进入循环,不断的将数组的中间键(mid)和被查找的键比较,若相等则返回mid,若不等则算法会把查找范围缩小一半
确定一个区间,使得目标值一定在区间中
确定一个性质,使得此性质是二段性的,即为将数组分为连续的两段,其中一段满足性质,另一段不满足
且答案是二段性的分界点
整数二分分为两大类
while(L<R){
M = (L+R+1)/2
if() L = M
else R = M-1
}
while(L<R){
M = (L+R)/2
if() R = M
else L = M+1
}
(1)左端点:整个数组中大于等于x的第一个位置q[mid]>=x
绿色区间即为大于等于x的区间,黄色区间是为x的区间
int lo = 0,hi = n-1;
while(l<r){//退出时l==r
int mid = l+r>>1;
if(q[mid]>=x)r=mid;
else l=mid+1;
}
if(q[r]==x){
cout<<r<<endl;
}
else{
cout<<-1<<endl;
}
(2)右端点:q[mid]<=x
int lo = 0,hi = n-1;
while(l<r){//退出时l==r
int mid = l+r+1>>1;
if(q[mid]<=x)l=mid;
else r=mid-1;
}
if(q[r]==x){
cout<<r<<endl;
}
else{
cout<<-1<<endl;
}
实数二分可以取到恰好的中点
可以直接将区间划分为[l,m],[m,r]
//求数的三次方根(精度1e-8)
#include<iostream>
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
double x;
cin>>x;
double l = -10000,r = 10000;
while (r-l>1e-8)
{
double mid = (l+r)/2;
if(mid*mid*mid>=x)r = mid;
else l = mid;
}
cout<<l<<endl;
return 0;
}
以上是脚本宝典为你收集整理的二分查找(包括查找元素是第一次和最后出现的位置)全部内容,希望文章能够帮你解决二分查找(包括查找元素是第一次和最后出现的位置)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。