数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

16 | 二分查找(下):如何快速定位IP对应的省份地址?

王争 2018-10-26
通过 IP 地址来查找 IP 归属地的功能,不知道你有没有用过?没用过也没关系,你现在可以打开百度,在搜索框里随便输一个 IP 地址,就会看到它的归属地。
这个功能并不复杂,它是通过维护一个很大的 IP 地址库来实现的。地址库中包括 IP 地址范围和归属地的对应关系。
当我们想要查询 202.102.133.13 这个 IP 地址的归属地时,我们就在地址库中搜索,发现这个 IP 地址落在 [202.102.133.0, 202.102.133.255] 这个地址范围内,那我们就可以将这个 IP 地址范围对应的归属地“山东东营市”显示给用户了。
[202.102.133.0, 202.102.133.255] 山东东营市
[202.102.135.0, 202.102.136.255] 山东烟台
[202.102.156.34, 202.102.157.255] 山东青岛
[202.102.48.0, 202.102.48.255] 江苏宿迁
[202.102.49.15, 202.102.51.251] 江苏泰州
[202.102.56.0, 202.102.56.255] 江苏连云港
现在我的问题是,在庞大的地址库中逐一比对 IP 地址所在的区间,是非常耗时的。假设我们有 12 万条这样的 IP 区间与归属地的对应关系,如何快速定位出一个 IP 地址的归属地呢?
是不是觉得比较难?不要紧,等学完今天的内容,你就会发现这个问题其实很简单。
上一节我讲了二分查找的原理,并且介绍了最简单的一种二分查找的代码实现。今天我们来讲几种二分查找的变形问题。
不知道你有没有听过这样一个说法:“十个二分九个错”。二分查找虽然原理极其简单,但是想要写出没有 Bug 的二分查找并不容易。
唐纳德·克努特(Donald E.Knuth)在《计算机程序设计艺术》的第 3 卷《排序和查找》中说到:“尽管第一个二分查找算法于 1946 年出现,然而第一个完全正确的二分查找算法实现直到 1962 年才出现。”
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(159)

  • Smallfly 置顶
    有三种方法查找循环有序数组
     
     一、
     1. 找到分界下标,分成两个有序数组
     2. 判断目标值在哪个有序数据范围内,做二分查找
     
     二、
     1. 找到最大值的下标 x;
     2. 所有元素下标 +x 偏移,超过数组范围值的取模;
     3. 利用偏移后的下标做二分查找;
     4. 如果找到目标下标,再作 -x 偏移,就是目标值实际下标。
     
     两种情况最高时耗都在查找分界点上,所以时间复杂度是 O(N)。
     
     复杂度有点高,能否优化呢?
     
     三、
    我们发现循环数组存在一个性质:以数组中间点为分区,会将数组分成一个有序数组和一个循环有序数组。
     
     如果首元素小于 mid,说明前半部分是有序的,后半部分是循环有序数组;
     如果首元素大于 mid,说明后半部分是有序的,前半部分是循环有序的数组;
     如果目标元素在有序数组范围中,使用二分查找;
     如果目标元素在循环有序数组中,设定数组边界后,使用以上方法继续查找。
     
     时间复杂度为 O(logN)。
    2018-10-27
    9
    254
  • zixuan
    思考题对应leetcode 33题,大家可以去练习
    2018-10-31
    1
    88
  • 舍得
    第一段代码有漏洞,且不说int能不能表示数组的下标问题,毕竟这个数组能越界说明相当庞大了;
    主要问题在于,如果我给定的数大于任何一个数组元素,low就会等于n,n是数组越界后的第一个元素,如果它刚好是要查找的值呢??

    作者回复: 谢谢指正 我稍后改下

    2018-10-27
    2
    25
  • 王艳红
    王老师,有一个疑惑不太明白
    int mid = low + ((high - low)>>1)
    这句,为什么要用这种写法呢?我看之前的简单的额二分查找是
    int mid = (low + high)/2

    作者回复: 下面的写法有可能会导致溢出,比如low很大,high也很大,之和就溢出了。

    2019-03-05
    3
    22
  • Victor
    今天的IP地址归属地问题,从工程实现的角度考虑,我更偏向于直接使用关系型数据库实现。
    也就是将12w条归属地与IP区间的开始、结束存入数据库中。
    数据库表ip_table有如下字段:area_name | start_ip | end_ip ,start_ip及end_ip 均建立索引
    SQL语句:
    select area_name from ip_table where input_ip >= start_ip and input_ip <= end_ip;
    学习算法的课程常常和自己工程开发的实际结合在一起,感觉两者是相互促进理解的过程。

    作者回复: 数据库可以 单性能会受限

    2018-10-27
    1
    15
  • charon
    用JavaScript实现的最基本的思考题:
    array是传入的数组,value是要查找的值
    思路是通过对比low,high的值来判断value所在的区间,不用多循环一遍找偏移量了~
        function search(array,value){
            let low = 0;
            let high = array.length - 1;
            
            while(low <= high){
                let mid = low + ((high - low) >> 1);
                if(value == array[low]) return low;
                if(value == array[high]) return high;
                if(value == array[mid]) return mid;

                if(value > array[mid] && value > array[high] && array[mid] < array[low]){
                    high = mid - 1;
                }else if(value < array[mid] && value < array[low] && array[mid] < array[low]){
                    high = mid - 1;
                }else if(value < array[mid] && value > array[low]){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }

            return -1
        }
    2018-10-26
    11
  • 姜威
    总结:二分查找(下)
    一、四种常见的二分查找变形问题
    1.查找第一个值等于给定值的元素
    2.查找最后一个值等于给定值的元素
    3.查找第一个大于等于给定值的元素
    4.查找最后一个小于等于给定值的元素
    二、适用性分析
    1.凡事能用二分查找解决的,绝大部分我们更倾向于用散列表或者二叉查找树,即便二分查找在内存上更节省,但是毕竟内存如此紧缺的情况并不多。
    2.求“值等于给定值”的二分查找确实不怎么用到,二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。
    三、思考
    1.如何快速定位出一个IP地址的归属地?
    [202.102.133.0, 202.102.133.255] 山东东营市
    [202.102.135.0, 202.102.136.255] 山东烟台
    [202.102.156.34, 202.102.157.255] 山东青岛
    [202.102.48.0, 202.102.48.255] 江苏宿迁
    [202.102.49.15, 202.102.51.251] 江苏泰州
    [202.102.56.0, 202.102.56.255] 江苏连云港
    假设我们有 12 万条这样的 IP 区间与归属地的对应关系,如何快速定位出一个IP地址的归属地呢?
    2.如果有一个有序循环数组,比如4,5,6,1,2,3。针对这种情况,如何实现一个求“值等于给定值”的二分查找算法?
    2018-11-03
    2
    7
  • 朱坤
    置顶的同学的思路一,即先找分界再判断在哪个数组,再二分,其实是可以做到O(Log N)的,找分界的点的规则就是找到首个小于a[0]的元素,思路用老师4个转换问题的解法就可以。按评论做了下leetcode33题,感觉会比较老师给的思考题描述清晰。。因为老师说的找问题,没有明确有几组循环数组。。
    2019-02-25
    6
  • 菜鸡程序员

    1.如果不知道分界点,找寻分界点没有意义,不如直接遍历。
    2.如果知道分界点,查看在哪一边,然后二分法,或者偏移量计算,二分法

    老师,我今天这种可以吗:
    /**
    * 功能描述:查找第一个大于等于给定值的元素
    *
    * @param null
    * @return
    * @author xiongfan
    * @date 2018/12/7 9:43:00
    */
    public static int getFirstGreaterValue(int[] array,int value) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
    int mid = low + (high - low) >> 1;
    if (array[mid] < value) {
    low = mid + 1;
    } else if (array[mid] > value) {
    high = mid - 1;
    } else {

    if (mid == 0 || array[mid - 1] < array[mid]) {
    return mid;
    }
    high = mid - 1;

    }
    }

    return low>array.length-1?-1:low;
    }

    /**
    * 功能描述:查找最后一个小于等于给定值的元素
    *
    * @param null
    * @return
    * @author xiongfan
    * @date 2018/12/7 10:03:00
    */
    public static int getLastLessValue(int[] array,int value) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
    int mid = low + (high - low) >> 1;
    if (array[mid] > value) {
    high = mid - 1;
    } else if (array[mid] < value) {
    low = mid + 1;
    } else {
    if (mid > array.length-1 || array[mid] < array[mid + 1]) {
    return mid;
    }
    low = mid + 1;
    }
    }

    return high<0?-1:high;
    }
    2018-12-07
    6
  • 狼的诱惑
    @老师,请老师或其他高人回复指教
    /**
         * 例如: 4 5 6 1 2 3
         * 循环数组的二分查找 总体时间复杂度O(n)
         */
        public static int forEqualsThan(int[] arr, int num) {
            if (arr[0] == num) {
                return 0;
            }
            int length = arr.length;
            int low = 0;
            int high = length - 1;
            //找到循环节点
            for (int i = 0; i < length; i++) {
                if (i == length - 1) {
                    if (arr[i] > arr[0]) {
                        low = i;
                        high = 0;
                        break;
                    }
                } else {
                    if (arr[i] > arr[i + 1]) {
                        low = i;
                        high = low + 1;
                        break;
                    }
                }
            }
            //判断第一个节点的大小位置,确定low和high的值,转变为正常有序的二分查找
            if (arr[0] < num) {
                high = low;
                low = 0;
            }
            if (arr[0] > num) {
                low = high;
                high = length - 1;
            }
            while (low <= high) {
                int index = low + ((high - low) >> 1);
                if (arr[index] > num) {
                    high = index - 1;
                }
                if (arr[index] < num) {
                    low = index + 1;
                }
                if (arr[index] == num) {
                    return index;
                }
            }
            return -1;
        }
    2018-10-31
    3
    5
  • 牛顿的苹果啦
    思考题:
    可以考虑将数组分为N个有序数组,分别进行二分查找。
    代码实现:
     public int circleBinarySearch(int[] a, int value){
            int low = 0, high=0;
            for(int i=0;i<a.length-1;i++){
                //找到有序数组的下标
                if(a[i]<a[i+1]){
                    high=i+1;
                }else{
                    //有序数组到顶,二分查找
                    int i1 = binarySearch(low, high, a, value);
                    if(-1 != i1){
                        return i1;
                    }else{
                        low = high+1;
                    }
                }
                //high已经到最后一个位置
                if(a.length-1 == high){
                    return binarySearch(low, high, a, value);
                }
            }
            return -1;
        }

        private int binarySearch(int low, int high, int[] a, int value){
            for(;low<=high;){
                int middle = low+((high-low)>>1);
                if(a[middle] == value){
                    return middle;
                }
                if(a[middle] > value){
                    high = middle -1;
                }else{
                    low = middle +1;
                }
            }
            return -1;
        }
    2019-01-31
    4
  • 晓杉
    老师,我有一个疑问。
    使用二分查找的前提是有序数组。
    对于本节IP地址问题,我们先进行排序再进行查找,我理解应该时间复杂度是排序平均O(nLogn)再加上二分查找O(logn)
    比单纯的顺序遍历O(n)要慢许多了。
    是不是实际中,这种无序情况直接使用了顺序遍历查找呢?
    2018-11-16
    2
    4
  • 勤劳的小胖子-libo
    1. 先二分遍历找到分隔点index,特征是<pre, >=next;
    2. 把数组分成二个部分,[0,index-1], [index,length-1];
    3. 分别使用二分查找,找到给定的值。
    时间复杂度为2*log(n). 不确定有什么更好的办法。
    2018-10-27
    4
  • komo0104
    给原来的index加上偏移量。
    比如原来的二分查找代码从0开始到n-1结束,现在为x到x - 1 (即n-1+x-n)。
    x为开始循环处的索引,例子里为3 (1所在索引)。需要扫描一遍数组找到x,复杂度O(n)。其余和普通二分查找一样,需要多判断index not out of bound。如果索引超过n了要减n。
    总的复杂度还是O(n)
    2018-10-26
    3
  • 低调人生
    我觉得查找第一个符合给定的值得那两种写法 第一种更好理解 没看懂作者的写法
    2019-05-28
    2
    2
  • 毅仔
    第一次见到逻辑这么清晰的二分查找代码,已经被老师俘获了,太优雅了
    2018-12-23
    2
  • QFann
    public int search(int[] nums, int target) {
            if(nums.length ==0) return -1;
            if(nums.length ==1){
                if(nums[0] == target) return 0;
                else return -1;
            }
            int low = 0;
            int high = nums.length - 1;
            int index = subIndex(nums,low,high);
            if(index != -1){
                int val = binarySearch(nums,low,index,target);
                if (val != -1) return val;
                return binarySearch(nums,index+1,high,target);
            }
            return binarySearch(nums,low,high,target);
        }
        
        public static int subIndex(int [] nums,int low,int high){
            while (low <= high){
                int mid = low + ((high - low )>> 1);
                if(nums.length < 1) return -1;
                if(nums[mid] > nums[mid+1]) return mid;
                else if( nums[mid] < nums[low] ) high = mid ;
                else if (nums[mid] > nums[high]) low = mid ;
                else return -1;
            }
            return -1;
        }
        
        public static int binarySearch(int[] nums,int low,int high,int target){
            while (low <= high){
                int mid = low + ((high - low)>>1);
                if(nums[mid] == target) return mid;
                else if (nums[mid] < target) low = mid + 1;
                else high = mid -1;
            }
            return -1;
        }
    2018-12-18
    2
  • Monday
    二分的四种变种写法。个人觉得都是分三种情况进行讨论,再多注意判断边界值,三种情况为:
    a[mid]<value
    a[mid]=value
    a[mid]>value;
    思考题:自己思考了一小段时间没有好的思路,就各学友的留言,亲自实现了Smallfly的方法三,感觉比较好!谢谢!
    2018-10-29
    2
  • Vilochen.
    文中的二分查找四道题实现:
    1.
    public static int searchFirst(int[] array, int num) {
            int l = 0;
            int h = array.length - 1;
            while (l < h) {
                int mid = (l + h) >>> 1;
                if (array[mid] < num) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            if (array[l] == num) {
                return l;
            }
            return -1;
        }

     2. public static int searchFirstLarge(int[] array, int num) {
            int l = 0;
            int h = array.length - 1;
            while (l < h) {
                int mid = (l + h) >>> 1;
                if (array[mid] < num) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            if (array[l] >= num) {
                return l;
            }
            return -1;
        }

      3. public static int searchLast(int[] array, int num) {
            int l = 0;
            int h = array.length - 1;
            while (l < h) {
                int mid = (l + h + 1) >>> 1;
                if (array[mid] > num) {
                    h = mid - 1;
                } else {
                    l = mid;
                }
            }
            if (array[l] == num) {
                return l;
            }
            return -1;
        }

     4. public static int searchLastSmall(int[] array, int num) {
            int l = 0;
            int h = array.length - 1;
            while (l < h) {
                int mid = (l + h + 1) >>> 1;
                if (array[mid] > num) {
                    h = mid - 1;
                } else {
                    l = mid;
                }
            }
            if (array[l] <= num) {
                return l;
            }
            return -1;
        }
    2019-11-18
    1
  • felix
    想到一种思路,依旧对半查找,但是现在两边会出现一个有序数组和循环数组,如果选择的数在有序数组内,正常的二分查找就OK,如果不是,继续对半,同上。次数和二分查找一致,所以依旧是logN,就是判断比较多点。
    2019-11-09
    1
收起评论
99+
返回
顶部