20 | 二分查找：提升程序的查找效率
胡光
你好，我是胡光，欢迎回来。
上节课，我们讲了链表的基础结构，以及体会了一把链表结构在思维逻辑层面的作用，就是面对看似复杂的问题，当我们把它转换成链表结构思维去解决的时候，这些问题和困难都迎刃而解。
今天呢，我将带你学习一种简单、有趣且高效的算法，叫做二分查找。在学习二分查找之前呢，有一个关于二分查找的笑话，你必须知道。
话说，在学校图书馆的计算机科学相关书籍借阅区里面，有一个女生抱着 40 本书往外走，经过图书馆安检机器的时候，安检机器发出了警报声。这时候，女生很无奈，就把书放到了地上，准备一本一本地去试，看看究竟是哪一本书没有消磁。
女生的举动，被旁边图书馆管理员阿姨看到了，阿姨看不下去了，叫住了她，说：这么一本一本的尝试，多慢啊！我教你一种方法。眼看阿姨将书分成两摞，拿起其中一摞的书，过了一下安检，安检机器响了，阿姨就又将这摞书分成了两部分，拿出其中一部分又过了一次安检……就这样，阿姨每次将书的数量减少一半，没几次就找到了那本没有消磁的书。阿姨得意洋洋地说：小姑娘，这就是书中讲的二分查找算法，你这专业知识不过关啊！次日，图书馆发现，丢了 39 本书。
上面这个故事中的阿姨，虽然知道二分查找算法，可明显是对使用算法的前提条件没有搞清楚。今天，我教给你的不仅是二分查找算法本身，还希望你能准确搞清楚二分查找算法的使用场景。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了二分查找算法及其延伸应用的相关内容。首先，文章介绍了二分查找算法的基本原理和示例代码，强调了其在有序数组中查找数字时的高效性。随后，引出了“二分答案”的思想，指出二分查找算法不仅适用于有序数组的查找问题，还能解决一些较为困难的问题，尤其适用于确定某一位为待查找值的位置。文章通过生动的故事和实际例子，生动地阐述了二分查找算法的原理和应用场景，使读者能够快速了解并掌握这一高效的查找算法。此外，文章还介绍了二分答案相关算法思想，并总结了二分算法框架的应用场景和特点。通过对“个人所得税计算”和“切出最长的绳子”等实际问题的分析，阐述了二分思想的重要性和灵活性。最后，文章强调了数组和函数在思维层面的相似性，并以一个笑话故事为例，说明了二分算法思想的误用场景。整体而言，本文通过生动的例子和实际问题的分析，使读者能够快速了解二分查找算法及其延伸应用的相关知识，为读者提供了一次全面的学习体验。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59
《人人都能学会的编程入门课》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(16)
- 最新
- 精选
1043
二分算法用在单调区间的增减计算比较快。不知道区间取值就会像图书馆阿姨一样丢了39/40本书…… 在题目中求f（x）=y，有限次二分计算中在给定y的情况求解x的问题就是多次取中尝试计算吗？就是经过log2n次计算就可以找到合适的答案……作者回复: 对的
2020-04-16
webmin# 通过税后工资计算税前工资 ```golang func TestReversePay(t *testing.T) { taxMatrix := []TaxRange{ TaxRange{Rate: 0.03, Start: 0, End: 3000, QuickValue: 90}, TaxRange{Rate: 0.1, Start: 3000, End: 12000, QuickValue: 900}, TaxRange{Rate: 0.2, Start: 12000, End: 25000, QuickValue: 2600}, TaxRange{Rate: 0.25, Start: 25000, End: 35000, QuickValue: 2500}, } //1.6 = 1 + 0.03 + 0.1 + 0.2 + 0.25 var coefficient float64 = 1.6 var pays []float64 = []float64{18600, 0.6, 600.6, 8600.6, 10600.6, 106000.15} for _, pay := range pays { income := pay - getTax(pay, taxMatrix) fmt.Println(fmt.Sprintf("income:%f", income)) fmt.Println(fmt.Sprintf("pay:%f", pay)) fmt.Println(fmt.Sprintf("ReversePay:%f", ReversePay(income*coefficient, income, taxMatrix))) fmt.Println("") } } type TaxRange struct { Rate float64 Start float64 End float64 QuickValue float64 } func ReversePay(pay, income float64, taxMatrix []TaxRange) float64 { guessIncome := pay - getTax(pay, taxMatrix) if math.Abs(guessIncome-income) <= 1e-7 { return pay } mid := math.Abs(guessIncome-income) / 2 if guessIncome > income { pay -= mid } else { pay += mid } return ReversePay(pay, income, taxMatrix) } func getTax(pay float64, taxMatrix []TaxRange) float64 { var tax float64 = 0 for _, taxRange := range taxMatrix { if pay > taxRange.End { tax += taxRange.QuickValue continue } tax += (pay - taxRange.Start) * taxRange.Rate break } return tax } ```作者回复: 这么计算的逻辑没问题。再试试用二分试试吧。
2020-04-032
宋不肥就是计算的结果不正确，相差了大概1000作者回复: 你想想哈，如果你 ff(mid) 比 x 小很多呢？？？那相减之后，是不是也是 <= EPS ? 所以，你要判断应该是 ff(mid) 与 x 之间差的绝对值是不是 <= EPS
2020-03-092- 宋不肥#include<stdio.h> //逆函数版本 double f(double x){ if(x <= 3000*0.97) return x/0.97; if(x <= (3000*0.97 + (12000-3000)*0.9 )) return ( x- 3000 * 0.97 ) / 0.9 + 3000; if(x <= (3000*0.97 + (12000-3000)*0.9 + (25000-12000)*0.8 ) ) return ( x- 3000 * 0.97 - (12000-3000)*0.9 ) / 0.8 + 12000 ; if(x <= (3000*0.97 + (12000-3000)*0.9 + (25000-12000)*0.8 + (35000-25000)*0.75 ) ) return ( x- 3000 * 0.97 - (12000-3000)*0.9 - ( 25000-12000 ) * 0.8 ) / 0.75 + 25000; else return -1; } //二分法版本 #define EPS 1e-7 double ff(double x){ if(x <= 3000) return x*0.97; if(x <= 12000) return ( x- 3000 ) / 0.9 + 3000*0.97; if(x <= 25000) return ( x- 12000 ) * 0.8 + 3000 * 0.97 + (12000-3000)*0.9 ; if(x <= 35000) return ( x- 25000 ) * 0.75 + 3000 * 0.97 + (12000-3000)*0.9 + (25000 - 12000)*0.8; else return -1; } double binary_search(double x, double l , double h ) { if (h - l <= EPS) return h; double mid = (h + l) / 2.0; if(ff(mid) == x) return mid; // 为什么这一行不能换为if(ff(mid) - x <= EPS) return mid; if (ff(mid) < x) return binary_search(x,mid, h); return binary_search(x, l, mid); } int main(){ double y; y = f(16290); printf("%f\n",y); y = binary_search(16290,0,35000); printf("%f",y); } 之前没注意，反函数想错了。 确实二分法 适合（对数时间复杂度） 这种单调函数 二分自变量来寻找目标因变量所对应的自变量的大小。 能避免求逆的繁琐过程出错。 但有个问题，二分法中的这一行代码，必须使用if(ff(mid) == x) return mid;为什么这一行换为if(ff(mid) - x <= EPS) return mid; 会得到错误结果
作者回复: 错误结果？能说明具体情况么？
2020-03-082 - 宋不肥#include<stdio.h> double f(double x){ if(x <= 3000*0.97) return x/0.97; if(x <= (3000*0.97 + (12000-3000)*0.9 )) return ( x- 3000 * 0.97 ) / 0.9 + 3000*0.97; if(x <= (3000*0.97 + (12000-3000)*0.9) + (25000-12000)*0.8 ) return ( x- 3000 * 0.97 - (12000-3000)*0.9 ) / 0.8 + 3000*0.97 +(12000-3000)*0.9 ; if(x <= (3000*0.97 + (12000-3000)*0.9) + (25000-12000)*0.8 + (35000-25000)*0.75 ) return ( x- 3000 * 0.97 - (12000-3000)*0.9 - ( 25000-12000 ) * 0.8 ) / 0.75 + 3000*0.97 +(12000-3000)*0.9 + ( 25000-12000 ) * 0.8; else return -1; } int main(){ double y; y = f(23534); printf("%f",y); }
作者回复: 代码有如下问题： 1、没有用到二分思想。 2、结果不正确，你测试一下文章中的 16290。
2020-03-07 
宋jia wen老师 个人所得税缴纳税率表里 如果我的工资是12000，那税率怎么算呢？作者回复: 12000-3000*0.03-（12000-3000）*0.1
2020-03-07
Hunter Liu老师的课一路跟下来，虽然有不懂的地方，但这可不是入门啊。作者回复: -_-|||，可能是我对入门这个概念理解的有点儿偏差。sorry，让你们受苦了。^_^
2020-03-06
Jinlee我的思路是这样的：由“个人所得税缴纳税率表”得到税后工资 y 与税前工资 x 的 分段函数关系式，再由每一段 x 的取值范围 得到每一段 y 的取值范围，这样就可以由 已知税后工资与 y 的比较来锁定待求税前工资 x 的取值范围以及对应的函数， 进而 用二分答案法取得待求税前工资的逼近值。 但是，，，没能实现代码，想了很久。作者回复: 『分段函数关系式，再由每一段 x 的取值范围 得到每一段 y 的取值范围，这样就可以由』 这一步完全多余~~~~想想是不是。
2020-03-04
奕由税后工资算税前工资：可以把每个区间的边界值当作数组的一个值，最后得到这样的一个数组 [0,3000,12000,25000,35000] 然后在按照二分法进行计算作者回复: (｡ì _ í｡)前一步操作比较多余。
2020-03-03
罗耀龙@坐忘茶艺师学编程 课文的例子，完整可运行程序 #include <stdio.h> #include <math.h> #define EPS 1e-7 double r[100] = {4, 5, 6}, n; /*切线段函数*/ int f(double x){ int cnt = 0; for (int i = 0; i < n; i++){ cnt += (int)floor(r[i] / x); } return cnt; } /*二分查找函数，可能是环境原因，这里只能的传入变量，而不能像老师那样直接传入数组（指针？）*/ double binary_search(double l, double r, int k){ if(r - l <= EPS)return r; double mid = (l + r) / 2.0; if(f(mid) < k) return binary_search(l, mid, k); return binary_search(mid, r, k); } int main(){ n = 3; double l = 0; int k = 7; double b; for(int i = 0; i < n; i++){ b = binary_search(l, r[i], k); } printf("线段最长为%lf", b); return 0; } 也许是环境问题，老师的传入数组的BS函数运行不了，我摸索出的方法是二分查找函数里还是传入变量，在主函数里在套一个循环来遍历所有的线段。2020-10-0512
收起评论
