二分查找算法详解

二分查找算法详解

ID:14173413

大小:57.00 KB

页数:7页

时间:2018-07-26

二分查找算法详解_第1页
二分查找算法详解_第2页
二分查找算法详解_第3页
二分查找算法详解_第4页
二分查找算法详解_第5页
资源描述:

《二分查找算法详解》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、二分查找算法详解二分查找算法,是一种在有序数组中查找某一特定元素的搜索算法。注意两点:(1)有序:查找之前元素必须是有序的,可以是数字值有序,也可以是字典序。为什么必须有序呢?如果部分有序或循环有序可以吗?(2)数组:所有逻辑相邻的元素在物理存储上也是相邻的,确保可以随机存取。 算法思想:搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表

2、找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 这里我们可以看到:(1)如果查找值和中间值不相等的时候,我们可以确保可以下次的搜索范围可以缩小一半,正是由于所有元素都是有序的这一先决条件(2)我们每次查找的范围都是理应包含查找值的区间,当搜索停止时,如果仍未查找到,那么此时的搜索位置就应该是查找值应该处于的位置,只是该值不在数组中而已 算法实现及各种变形:1.非降序数组A,查找任一个 值==val的元素,若找到则返回下标位置,若未找到则返回-12.非降序数组A,查找第一个 值==val的元素,若找到则

3、返回下标位置,若未找到则返回-1(类似:查找数组中元素最后一个小于val值的位置)3.非降序数组A,查找最后一个值==val的元素,若找到则返回下标位置,若未找到则返回-1 (类似:查找数组中元素第一个大于val值的位置)4.非降序数组A,查找任一值为val的元素,保证插入该元素后数组仍然有序,返回可以插入的任一位置5.非降序数组A,查找任一值为val的元素,保证插入该元素后数组仍然有序,返回可以插入的第一个位置6.非降序数组A,查找任一值为val的元素,保证插入该元素后数组仍然有序,返回可以插入的最后一个

4、位置7.非降序数组A,查找任一个 值==val的元素,若找到则返回一组下标区间(该区间所有值==val),若未找到则返回-18. 非降序字符串数组A,查找任一个 值==val的元素,若找到则返回下标位置,若未找到则返回-1(类似:未找到时返回应该插入点)9.循环有序数组中查找==val的元素,若找到则返回下标位置,若未找到则返回-1 1.非降序数组A,查找任一个 值==val的元素,若找到则返回下标位置,若未找到则返回-11intbinary_search(int*a,intlen,intval)2{3as

5、sert(a!=NULL&&len>0);4intlow=0;5inthigh=len-1;6while(low<=high){7intmid=low+(high-low)/2;8if(vala[mid]){11low=mid+1;12}else{13returnmid;14}15}16return-1;17}注意:(1)使用assert对函数输入进行合法性检查(2)while循环的条件是low<=high,这里如果查找值未找到,则此时一

6、定low=high+1 (3)对val和a[mid]做比较时,首先考虑不等情况,最后考虑相等情况,如果随机分布的话不等的概率肯定大于相等的概率 2.非降序数组A,查找第一个 值==val的元素,若找到则返回下标位置,若未找到则返回-1(类似:查找数组中元素最后一个小于val值的位置)因为数组中可能有重复元素,所以数组中是有可能存在多个值与val相等的,我们对普通二分进行变形:当vala[mid]时,接下来的搜索范围减半 low =mid+

7、1当val==a[mid]时,这个时候就不能简单的返回了,我们要求的是第一个==val的值,什么条件下是第一个呢?               当mid==0那当然是第一个               当mid>1&&a[mid-1]!=val这个时候也是第一个               其他情况下,这个时候查找到的值不是第一个,此时我们应该继续搜索,而不是返回,搜索范围是什么呢?因为是查找第一个,那么接下来肯定应该在               此时位置的左边继续搜索,即high=mid-11intse

8、arch_first(int*a,intlen,intval)2{3assert(a!=NULL&&len>1);4intlow=0;5inthigh=len-1;6while(low<=high){7intmid=low+(high-low)/2;8if(vala[mid]){11low=mid+1;12}else{13if(mid==0)r

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。