二分查找总结

  • A+
所属分类:算法与数据结构

二分查找总结

基本的二分查找:值等于给定值

没有重复值

循环实现:

递归实现:

优点

时间复杂度为O(logn) 空间复杂度O(1)

缺点

只能用于线性表数组,不能用于链表,因为二分法要用到按照数组下标随机访问元素,数组的随机访问时间复杂度为O(1), 而链表的随机访问时间复杂度为O(n),(如果将二分法用于链表 那么二分法的时间复杂度为O(n))。

数据必须要有序的。要对数据进行排序,如果是静态数据,一次排序后,随着查找增多,可以平摊排序的成本。如果频繁插入 删除,二分查找不适合。

数据量太小不适合二分查找 顺序查找即可。

数据量太大不适合二分查找 二分查找依赖于数组这种数据结果,数组需要一块连续的内存空间来储存数据,如果数据量太大,可能申请不到连续的内存空间来储存数据。

查找第一个值等于给定值的元素

代码一:

代码二:

查找最后一个值等于给定值的元素

代码一:

代码二:

查找第一个大于等于给定值的元素

查找最后一个小于等于给定值的元素

应用

快速定位IP对应的省份地址

现在这个问题应该很简单了。 如果 IP区间与归属地的对应关系不经常更新, 我们可以先预处理这
12 万条数据, 让其按照起始 IP从小到大排序。 如何来排序呢? 我们知道, IP地址可以转化为 32
位的整型数。 所以, 我们可以将起始地址, 按照对应的整型值的大小关系, 从小到大进行排序。
然后, 这个问题就可以转化为我刚讲的第四种变形问题
在有序数组中, 查找最后一个小于等于某个
给定值的元素
了。

当我们要查询某个 IP归属地时, 我们可以先通过二分查找, 找到最后一个起始 IP小于等于这个 IP
IP区间, 然后, 检查这个 IP是否在这个 IP区间内, 如果在, 我们就取出对应的归属地显示; 如
果不在, 就返回未查找到。

LTXU

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: