数据结构与算法之美
王争
前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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?

王争 2018-10-24
今天我们讲一种针对有序数据集合的查找算法:二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,很多非计算机专业的同学很容易就能理解,但是看似越简单的东西往往越难掌握好,想要灵活应用就更加困难。
老规矩,我们还是来看一道思考题。
假设我们有 1000 万个整数数据,每个数据占 8 个字节,如何设计数据结构和算法,快速判断某个整数是否出现在这 1000 万数据中? 我们希望这个功能不要占用太多的内存空间,最多不要超过 100MB,你会怎么做呢?带着这个问题,让我们进入今天的内容吧!

无处不在的二分思想

二分查找是一种非常简单易懂的快速查找算法,生活中到处可见。比如说,我们现在来做一个猜字游戏。我随机写一个 0 到 99 之间的数字,然后你来猜我写的是什么。猜的过程中,你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。你来想想,如何快速猜中我写的数字呢?
假设我写的数字是 23,你可以按照下面的步骤来试一试。(如果猜测范围的数字有偶数个,中间数有两个,就选择较小的那个。)
7 次就猜出来了,是不是很快?这个例子用的就是二分思想,按照这个思想,即便我让你猜的是 0 到 999 的数字,最多也只要 10 次就能猜中。不信的话,你可以试一试。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(130)

  • Jerry银银 置顶
    说说第二题吧,感觉争议比较大:
    假设链表长度为n,二分查找每次都要找到中间点(计算中忽略奇偶数差异):
    第一次查找中间点,需要移动指针n/2次;
    第二次,需要移动指针n/4次;
    第三次需要移动指针n/8次;
    ......
    以此类推,一直到1次为值

    总共指针移动次数(查找次数) = n/2 + n/4 + n/8 + ...+ 1,这显然是个等比数列,根据等比数列求和公式:Sum = n - 1.

    最后算法时间复杂度是:O(n-1),忽略常数,记为O(n),时间复杂度和顺序查找时间复杂度相同

    但是稍微思考下,在二分查找的时候,由于要进行多余的运算,严格来说,会比顺序查找时间慢


    -----------------
    以上分析,不知道是否准确,还请老师解答

    作者回复: 分析的很好 👍 同学们可以把这条顶上去了

    2018-10-25
    6
    498
  • 蒋礼锐 置顶
    因为要精确到后六位,可以先用二分查找出整数位,然后再二分查找小数第一位,第二位,到第六位。

    整数查找很简单,判断当前数小于+1后大于即可找到,

    小数查找举查找小数后第一位来说,从x.0到(x+1).0,查找终止条件与整数一样,当前数小于,加0.1大于,

    后面的位数以此类推,可以用x*10^(-i)通项来循环或者递归,终止条件是i>6,

    想了一下复杂度,每次二分是logn,包括整数位会查找7次,所以时间复杂度为7logn。空间复杂度没有开辟新的储存空间,空间复杂度为1。

    没有具体用代码实现,只是思路,还请多多指正。之后会用js去实际实现。
    2018-10-24
    1
    45
  • Jerry银银
    个人觉得二分查找进行优化时,还个细节注意:
    将mid = lo + (hi - lo) /2,将除法优化成移位运算时,得注意运算符的优先级,千万不能写成这样:mid = lo + (hi - lo) >> 1

    作者回复: 👍

    2018-10-26
    6
    136
  • 朱凯
    二分法求一个数x的平方根y?
    解答:根据x的值,判断求解值y的取值范围。假设求解值范围min < y < max。若0<x<1,则min=x,max=1;若x=1,则y=1;x>1,则min=1,max=x;在确定了求解范围之后,利用二分法在求解值的范围中取一个中间值middle=(min+max)÷2,判断middle是否是x的平方根?若(middle+0.000001)*(middle+0.000001)>x且(middle-0.000001)*(middle-0.000001)<x,根据介值定理,可知middle既是求解值;若middle*middle > x,表示middle>实际求解值,max=middle; 若middle*middle < x,表示middle<实际求解值,min =middle;之后递归求解!
    备注:因为是保留6位小数,所以middle上下浮动0.000001用于介值定理的判断
    2018-10-25
    1
    87
  • Alexis何春光
    现在在cmu读研,正在上terry lee的data structure,惊喜的发现不少他讲的点你都涵盖了,个别他没讲到的你也涵盖了.... (当然可能因为那门课只有6学时,时间不足,但还是给这个专栏赞一个!)

    作者回复: 读cmu 太厉害了 仰慕

    2018-11-12
    7
    75
  • Dwyane
    1、low=mid+1,high=mid-1 学习了比较严谨条件


    2、二分法求根号5

    a:折半:       5/2=2.5

    b:平方校验:  2.5*2.5=6.25>5,并且得到当前上限2.5

    c:再次向下折半:2.5/2=1.25

    d:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25

    e:再次折半:2.5-(2.5-1.25)/2=1.875

    f:平方校验:1.875*1.875=3.515625<5,得到当前下限1.875

    每次得到当前值和5进行比较,并且记下下下限和上限,依次迭代,逐渐逼近平方根:
    2018-12-21
    1
    42
  • 锐雨
    求平方根,可以参考0到99之间猜数字的思路,99换成x, 循环到误差允许内即可,注意1这个分界线。欢迎交流,Java如下
    public static double sqrt(double x, double precision) {
    if (x < 0) {
    return Double.NaN;
    }
    double low = 0;
    double up = x;
    if (x < 1 && x > 0) {
    /** 小于1的时候*/
    low = x;
    up = 1;
    }
    double mid = low + (up - low)/2;
    while(up - low > precision) {
    if (mid * mid > x ) {//TODO mid可能会溢出
    up = mid;
    } else if (mid * mid < x) {
    low = mid;
    } else {
    return mid;
    }
    mid = low + (up - low)/2;
    }
    return mid;
    }
    2018-10-24
    1
    27
  • 三忌
    def sqrt(x):
        '''
        求平方根,精确到小数点后6位
        '''
        low = 0
        mid = x / 2
        high = x
        while abs(mid ** 2 - x) > 0.000001:
            if mid ** 2 < x:
                low = mid
            else:
                high = mid
            mid = (low + high) / 2
        return mid
    2018-10-24
    5
    25
  • 姜威
    总结:二分查找(上)
    一、什么是二分查找?
    二分查找针对的是一个有序的数据集合,每次通过跟区间中间的元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间缩小为0。
    二、时间复杂度分析?
    1.时间复杂度
    假设数据大小是n,每次查找后数据都会缩小为原来的一半,最坏的情况下,直到查找区间被缩小为空,才停止。所以,每次查找的数据大小是:n,n/2,n/4,…,n/(2^k),…,这是一个等比数列。当n/(2^k)=1时,k的值就是总共缩小的次数,也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较,所以,经过k次区间缩小操作,时间复杂度就是O(k)。通过n/(2^k)=1,可求得k=log2n,所以时间复杂度是O(logn)。
    2.认识O(logn)
    ①这是一种极其高效的时间复杂度,有时甚至比O(1)的算法还要高效。为什么?
    ②因为logn是一个非常“恐怖“的数量级,即便n非常大,对应的logn也很小。比如n等于2的32次方,也就是42亿,而logn才32。
    ③由此可见,O(logn)有时就是比O(1000),O(10000)快很多。
    三、如何实现二分查找?
    1.循环实现
    代码实现:
    public int binarySearch1(int[] a, int val){
    int start = 0;
    int end = a.length - 1;
    while(start <= end){
    int mid = start + (end - start) / 2;
    if(a[mid] > val) end = mid - 1;
    else if(a[mid] < val) start = mid + 1;
    else return mid;
    }
    return -1;
    }
    注意事项:
    ①循环退出条件是:start<=end,而不是start<end。
    ②mid的取值,使用mid=start + (end - start) / 2,而不用mid=(start + end)/2,因为如果start和end比较大的话,求和可能会发生int类型的值超出最大范围。为了把性能优化到极致,可以将除以2转换成位运算,即start + ((end - start) >> 1),因为相比除法运算来说,计算机处理位运算要快得多。
    ③start和end的更新:start = mid - 1,end = mid + 1,若直接写成start = mid,end=mid,就可能会发生死循环。
    2.递归实现
    public int binarySearch(int[] a, int val){
    return bSear(a, val, 0, a.length-1);
    }
    private int bSear(int[] a, int val, int start, int end) {
    if(start > end) return -1;
    int mid = start + (end - start) / 2;
    if(a[mid] == val) return mid;
    else if(a[mid] > val) end = mid - 1;
    else start = mid + 1;
    return bSear(a, val, start, end);
    }
    四、使用条件(应用场景的局限性)
    1.二分查找依赖的是顺序表结构,即数组。
    2.二分查找针对的是有序数据,因此只能用在插入、删除操作不频繁,一次排序多次查找的场景中。
    3.数据量太小不适合二分查找,与直接遍历相比效率提升不明显。但有一个例外,就是数据之间的比较操作非常费时,比如数组中存储的都是长度超过300的字符串,那这是还是尽量减少比较操作使用二分查找吧。
    4.数据量太大也不是适合用二分查找,因为数组需要连续的空间,若数据量太大,往往找不到存储如此大规模数据的连续内存空间。
    五、思考
    1.如何在1000万个整数中快速查找某个整数?
    ①1000万个整数占用存储空间为40MB,占用空间不大,所以可以全部加载到内存中进行处理;
    ②用一个1000万个元素的数组存储,然后使用快排进行升序排序,时间复杂度为O(nlogn)
    ③在有序数组中使用二分查找算法进行查找,时间复杂度为O(logn)
    2.如何编程实现“求一个数的平方根”?要求精确到小数点后6位?
    2018-10-31
    1
    20
  • Smallfly
    1. 求平方根可以用二分查找或牛顿迭代法;
    2. 有序链表的二分查找时间复杂度为 O(n)。
    2018-10-24
    16
  • THROW
    1000w数据查找这个,在排序的时候不就可以找到了么?

    作者回复: 如果是多次查找操作呢

    2018-10-24
    1
    16
  • Victor
    开篇的问题:1000w 个 8字节整数的中查找某个整数是否存在,且内存占用不超过100M ? 我尝试延伸了一些解决方案:
    1、由于内存限制,存储一个整数需要8字节,也就是 64 bit。此时是否可以考虑bitmap这样的数据结构,也就是每个整数就是一个索引下标,对于每一个索引bit,1 表示存在,0 表示不存在。同时考虑到整数的数据范围,8字节整数的范围太大,这是需要考虑压缩的问题,压缩方案可以参考 RoaringBitmap 的压缩方式。
    2、我们要解决的问题,也就是判断某个元素是否属于某个集合的问题。这里是否可以和出题方探讨是否严格要求100%判断正确。在允许很小误差概率的情景下(比如判断是否在垃圾邮件地址黑名单中),可以考虑 BloomFilter 。
    BloomFilter 存储空间更加高效。1000w数据、0.1%的误差下需要的内存仅为 17.14M
    时间复杂度上,上面两种都是 hashmap的变种,因此为 o(1)。
    2018-10-27
    9
  • kaka
    关于求平方根的题,我知道一种比较巧妙的方法,那就是利用魔数,时间复杂度是 O(1),根据我测试,精度大概能精确到 5 位小数,也还不错。下面是 c 语言代码

    float q_rsqrt(float number) {
        int i;
        float x2, y;
        const float threehalfs = 1.5;
        x2 = number * 0.5;
        y = number;
        i = *(int*)&y;
        i = 0x5f3759df - (i >> 1);
        y = *(float*)&i;
        y = y * (threehalfs - (x2 * y * y));
        y = y * (threehalfs - (x2 * y * y));
        y = y * (threehalfs - (x2 * y * y));

        return 1.0 / y;
    }
    2018-10-29
    8
  • 啊波次的额佛哥~
    平方根C代码,precision位数,小数点后6位是0.000001
    double squareRoot(double a , double precision){
        double low,high,mid,tmp;
        if (a>1){
            low = 1;
            high = a;
        }else{
            low = 1;
            high = a;
        }
        while (low<=high) {
            mid = (low+high)/2.000;
            tmp = mid*mid;
            if (tmp-a <= precision && tmp-a >= precision*-1){
                return mid;
            }else if (tmp>a){
                high = mid;
            }else{
                low = mid;
            }
        }
        return -1.000;
    }
    int main(int argc, const char * argv[]) {
        double num = squareRoot(2, 0.000001);
        printf("%f",num);
        return 0;
    }
    2018-10-29
    2
    5
  • Liam
    链表的二分查找,每次查找的时间复杂度都为当前数据规模的一半,所以最坏情况下:
    查找次数f(n) = n + n/2 + n/4 + n/8 + ... + 1 = n(1 + 1/2 + 1/4 + ... 1/n)

    情况1: n = 2^k, 根据等比数列公式 f(n) = 2^k * ( 1 - (1/2) ^k) / (1 - 1/2) = 2n - 1
    情况2:n != 2^k, 假设k无穷大,则limf(n) = n ( 1 / (1 - 1/2)) = 2n, 实际上k < +∞, 所以
    f(n) < lim f(n) = 2n => f(n) = 2n-1

    综上所述,f(n) = 2n - 1, 时间复杂度为O(n)
    2018-10-26
    4
  • 追风者
    王老师,考研的话可以以这个课程作为数据结构第一轮的基础复习吗。如果可以,还需要补充其他概念知识吗

    作者回复: 概念知识应该全了 考研的话还要看看考纲吧

    2018-10-24
    4
  • 王小李
    平方根可以用牛顿迭代实现。

    作者回复: 哈哈 同学的回答超纲了 👍

    2018-10-24
    4
  • 刘伟、
    关于1000万数中快速查找某个整数,我有个想法。考虑用数组下标来存储数据,一个bit位来存储标记。第一次排序的时候能得到这组数的最大值和最小值。 假如最小是5,最大是2000万。那我们定义一个字节数组Byte arr[2000万],因为我只需要打标记,所以一个bit能存下标记,一个byte能存8个数。只需要2MB多一点就能存2000万个数的状态(存在还是不存在)
    先把这1000万个数存进去,用数x/8得到下标。用数x%8得到余数,因为每8个数一组得到的数组下标相同,所以还需要通过余数来确定具体是哪一个数。之后开始设置状态,从低位到高位,每一位代表一个数的状态,case0到7,每一次设置当下号码的状态时,先用按位于计算把其他不相关位置为1,当前位置为0,然后按位或对当前位置设置状态。存在就设置位1 ,不存在就设置位0
    上述操作执行完之后,就支持任意查找了。只需要输入一个数x,我就能立刻通过x/8和x%8得到当前这个数的位置,然后把这个位置的状态位数字取出来。如果是1表示存在,如果是0表示不存在。
    不知道这个想法有没有什么漏洞。希望老师或者一起学习的同学能帮忙一起想想

    作者回复: 赞 不错!

    2019-06-02
    3
  • yu🐟
    /**
         * 求一个数的平方根
         *
         * @param n:待求的数
         * @param deltaThreshold 误差的阈值
         * @return
         */
        public static double getSqureRoot(int n, double deltaThreshold) {
            double low = 1.0;
            double high = (double) n;
            while (low <= high) {
                double mid = low + ((high - low) / 2);
                double square = mid * mid;
                double delta = Math.abs(square / n - 1);
                if (delta < deltaThreshold) {
                    return mid;
                } else if (square < n) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            return -1.0;
        }
    2019-01-03
    2
    3
  • Kudo
    二分查找Python实现:
    1、非递归方式
    def bsearch(ls, value):
        low, high = 0, len(ls)-1
        while low <= high:
            mid = low + (high - low) // 2
            if ls[mid] == value:
                return mid
            elif ls[mid] < value:
                low = mid + 1
            else:
                high = mid - 1
        return -1

    2、递归方式
    def bsearch(ls, value):
        return bsearch_recursively(ls, 0, len(ls)-1, value)
        
    def bsearch_recursively(ls, low, high, value):
        if low > high:
            return -1
        mid = low + (high - low) // 2
        if ls[mid] == value:
            return mid
        elif ls[mid] < value:
            return bsearch_recursively(ls, mid+1, high, value)
        else:
            return bsearch_recursively(ls, low, mid-1, value)
    2018-10-25
    3
收起评论
99+
返回
顶部