网站分为哪几类,php网站开发 知乎,建立网站解析会员视频是犯什么罪,wordpress sql root文章目录一. 前提二. 基本思路三. 代码实现四. 封装在STL中的二分查找算法五. 浮点数二分一. 前提
待查找的序列是有序的#xff1b;待查找的 a 采取顺序存储结构。
二. 基本思路
设在升序序列 a [ low…high ] 查找的 k #xff0c; 首先找中间值 mid a [ ( lowhigh )/2 …
文章目录一. 前提二. 基本思路三. 代码实现四. 封装在STL中的二分查找算法五. 浮点数二分一. 前提
待查找的序列是有序的待查找的 a 采取顺序存储结构。
二. 基本思路
设在升序序列 a [ low…high ] 查找的 k 首先找中间值 mid a [ ( lowhigh )/2 ] ; 然后比较 k 和 a [ mid ] , 分成三个情况 1k a[ mid ] , 直接返回 a [ mid ] ; 2k a [ mid ] , 新的查找区域变为左子表 a [ low , mid-1 ] ; 3k a [ mid ] , 新的查找区域变为右子表 a [ mid1 , high ] ; 下一次查找根据 新的查找区间 进行查找。
三. 代码实现
//二分查找法
int BinSearch(int a[],int low,int high,int k)
{if(lowhigh){ //当前区间存在元素 int mid(lowhigh)/2;if(a[mid]k)return mid; //找到后返回其下标 if(a[mid]k)return BinSearch(int a[],int low,int mid-1,int k);if(a[mid]k)return BinSearch(int a[],int mid1,int high,int k);}else{return -1; //区间不存在元素返回 -1 }
}可见二分查找的时间重要花费在元素比较上其时间复杂度为O(log2n\log_{2}nlog2n) 四. 封装在STL中的二分查找算法
lower_bound
ForwoardIterator lower_bound( ForwoardIterator begin , ForwoardIterator end , const T num)lower_bound( begin,end,num)从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound ForwoardIterator upper_bound( ForwoardIterator begin , ForwoardIterator end , const T num)upper_bound( begin,end,num)从数组的begin位置到end-1位置二分查找第一个大于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 binary_search
bool binary_bound( ForwoardIterator begin , ForwoardIterator end , const T num)区间中存在要查找的值返回 true 否则 false 五. 浮点数二分
1.求n的平方根保留6位小数
#includebits/stdc.h
using namespace std;int main()
{double n;cinn;double l0,rn;while(r-l1e-8){ //负的别忘double mid(lr)/2;if(mid*midn) rmid;else lmid;}printf(%lf,l);return 0;}
