数据结构--折半查找法|数据结构--折半查找法 详解
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语言)
上面的bsget函数就用了折半查找法:
输出:
【数据结构--折半查找法|数据结构--折半查找法 详解】转载于:https://www.cnblogs.com/nvd11/archive/2013/04/02/2996791.html
推荐阅读
- 《数据结构与算法之美》——队列
- 超好用的PubMed文献查找管理插件—Scholarscope
- Elasticsearch|Elasticsearch 简介
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- Java深入了解数据结构之栈与队列的详解
- Java集合框架|Java集合框架 数据结构
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- 一个好的算法应该如何评测（数据结构学习1）
- XS-Java数据结构和算法目录总纲【2020-10-24~2021-2-12】