注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

饥民2011

一直在搬砖

 
 
 

日志

 
 
 
 

数据结构--折半查找法 详解  

2013-02-12 18:08:45|  分类: Data structure |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        1. 折半查找法定义
         折半查找法,也称为二分查找法, 二分搜索, 是一种在有序数组中查找某一特定元素的搜索算法.搜索过程中从数组的中间元素开始, 如果中间元素正好是要查找的元素, 则搜索过程结束;如果某一特定元素大于或者小于中间元素, 则在数组大于或小雨元素的那一半中查找, 而且跟开始一样从中间元素开始比较. 若某1个步骤中数组为空, 则代表找不到. 这种搜索算法每一次比骄傲都使搜索范围缩小一半.

          -- 摘自维基百科.


         2. 折半查找法分析
         从定义中可以看出折半查找法有几个特性.

         2.1 先决条件: 要搜索的数据已经排好序
         当然, 怎样将数据排序也是1个算法, 这里先不考究了, 但是要使用折半查找法, 这个条件是必需满足的

         2.2 折半查找法适合海量数据查找
      
折半查找法每执行1次.就会抛弃一半的无用数据, 如果数据很少的话,其实比线性查找快不了多少, 但是数据量很大的话, 抛弃的一半无用数据就很客观了!   相对于线性查找中节省了这一半数据的遍历时间啊.

         2.3 折半查找法算法复杂度
      
假如要查找数据的数量是n, 查找的次数为x,那么查找1次(x=1), 剩下的数据量就是 (n-1)/2 = n/2 -1/2了
         当x=2 时  剩下的数据量就是  n/4 - 3/4
         当x=3 时  剩下的数据量就是  n/8 - 7/8

         所以剩下的数据量R =  n/2^x   - 1 + 1/2^x

          当x很大时,  R就~= n/2^x -1 了

          那么什么时候才会肯定会找出要找的数据呢, 或者缺认该数据不存在呢.
          就是当剩余的数据量R=0 时啊.

           这时  n/2^x -1 =0  => 2^x = n => x= log2^n   (底为2,幂为n的对数)
           所以算法复杂度就是  O(log2^n)
           比起线性查找的算法复杂度O(n) , 优胜很多了.(如果n很大的话)

       3. 折半查找法的一个实现例子(c语言)
数据结构--折半查找法 详解 - 饥民 - 饥民2011

上面的bsget函数就用了折半查找法:
输出:
数据结构--折半查找法 详解 - 饥民 - 饥民2011
 
  评论这张
 
阅读(693)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017