本文共 1864 字，大约阅读时间需要 6 分钟。
针对有序数据的查找算法，每次与集合的中间值进行比较，大于中间值，递归在右边集合中查找，反之从左边集合中查找，直到查找到元素，或者查找区间被缩小到0；
二分查找，假设区间缩小到最后一个元素才找到，那么每次缩小区间1/2，所以总共缩小了 logn 次，所以时间复杂度就是 o( logn )，这是一个极其高效的时间复杂度；
简单的二分查找，有几个适用条件；
有序数据 没有重复数据 适用于数组存储结构，不适用于链表结构，因为链表进行下标随机访问，时间复杂度会达到 o(n) 不适合于频繁插入，删除数据的场景，因为要维护数组元素有序，涉及数据搬移，时间成本高 数据量太小，直接顺序查找就可以了 数据量太大，也不太适合二分查找，因为需要用数组存储，需要连续内存空间
如果二分查找的有序集合中，有重复数据时，就需要用到二分查找的变形；
查找第一个值等于给定值的元素；
与简单二分查找类似，只不过查找元素和 mid 元素对比完之后 如果大于或小于 mid，与之前逻辑一样 如果等于 mid，查看下 mid -1 是否等于查找元素，如果等于，继续在左边集合查找，如果不等于，mid 即为第一个等于 另外注意 mid = 0,即为所求
与 2 类似，如果大于或小于 mid，与之前逻辑一样 如果等于 mid，查看下 mid + 1 是否等于查找元素，如果等于，继续在右边集合查找，如果不等于，mid 即为最后一个等于
与 2 类似，如果大于 mid,与之前逻辑一样 如果小于 mid，查看下 mid -1 是否小于查找元素，如果确实小于，那么 mid 就为第一个大于给定值的元素，其他情况都继续 在左边集合查找 如果等于 mid，查看下 mid -1 是否等于查找元素，如果等于，继续在左边集合查找，如果不等于，mid 即为第一个等于
与 2 类似，如果 mid 大于给定值，继续左边集合查找 如果 mid 小于给定值，查看 mid + 1 是否大于给定值，如果大于，那么 mid 即为最后一个小于给定值的元素，其他情况继续 在右边集合查找 如果 mid 等于给定值，查看 mid +1 是否大于给定值，如果大于，那么 mid 即为一个等于给定值的元素，其他情况继续在有 右边集合查找
可以将 20 万个 ip 区间的首地址取出，然后进行排序组成一个有序集合 排序可以使用基数排序，从后到前，每一位进行计数排序 然后查找第一个大于等于给定值的元素 得到该元素后，如果是等于，即使用该区间对应的归属地即可，否则取该元素上一个元素区间对应的归属地
因为二分查找，只支持数组结构，对于链表结构，可以改造成跳表结构，提高查找效率；
在数据有序的链表数据上，每几个元素，提升一个元素组成索引层，就是跳表结构，查找时，先在索引层锁定范围，然后下降到下层节点查找数据；
索引层还可以再抽出节点，再建立一层索引，跳表查询的时间复杂度是 o( logn )；
如果按照2个节点抽出一个节点，组成索引层，然后索引层，也按照2个节点抽出一个节点，如此组成多级索引 第 k 级索引有 n/2^k 个节点，假设要求最高层索引有两个节点，那么 n/2^k = 2,得到 k = logn -1 所以链表的高度，就是 logn 每层最多需要遍历 3 个节点，是因为每一级索引和下层元素，间隔只有三个元素，从2个元素开始，确定一个区间后，只需在下 层，每层遍历 3 个节点即可 所以总的时间复杂度，就是 o(3logn),即 o(logn)
跳表的空间复杂度是 O( n )，每层节点数是 n/2 + n/4 + … + 2 = o( n )；
跳表的插入和删除操作，因为要保证跳表数据的有序性，因此首先要查找要插入元素的位置，时间复杂度是 o( logn )，单纯插入的时间复杂度是 o( 1 )，所以总的时间复杂度就是 o( logn )；
redis 中有序集合，就是用跳表实现的，因为 redis 常用的一个操作是，按照区间查找数据，这种操作在红黑树等有序结构中，实现比较复杂，而在跳表中，只需找到区间最小值，然后依次向后遍历即可，非常高效；
转载地址：http://lsfin.baihongyu.com/