【简约而不简单：神级代码的小秘密】| 第五章 二分查找

【简约而不简单：神级代码的小秘密】| 第五章 二分查找

某次节目中，杨二牛幸运的抽到了上台参与节目的机会。主持人在大屏幕上给出了一个是73。杨二牛背对屏幕看不到数字具体是几。主持人告诉了杨二牛：

1. 数字在1到100之间

2. 杨二牛需要在1到100间随机选择数字进行猜测，10次以内猜对了就能获得大奖

3. 如果杨二牛猜错了，主持人会告诉他猜测的数字是比目标数字大还是小

3. 猜中就能获得全套家电大奖

如果按顺序猜，只要第一个猜的不是结果的上下10个数字，大概率是拿不到奖的。

聪明的杨二牛不假思索的给了几个数字，然后轻而易举的拿到了大奖。事后记者采访时，杨二牛轻轻一笑：不用猜那么多次就一定可以拿到奖，赞助商金主爸爸真的是个非常可爱的慈善家呢。

杨二牛为什么会这样说呢？他可能是怎么猜的？

福尔摩斯说，排除所有不可能的因素之后,无论剩下的多么难以置信,那就是真相。

杨二牛第1次猜了50，主持人说“小了”，于是杨二牛就知道：那这个数一定在51到100之间；杨二牛第2次猜75，主持人说“大了”，于是杨二牛知道这个数应该在 1到74，结合第一次猜测情况，得到范围51到74；杨二牛第3次猜63，主持人说“小了”，于是杨二牛知道这个数应该在64到74；杨二牛第4次猜69，主持人说“小了”，于是杨二牛知道这个数应该在70到74；杨二牛第5次猜72，主持人说“小了”，于是杨二牛知道这个数应该在73到74；杨二牛第6次猜73，主持人说“猜对了”，于是拿到了大奖。

这就是二分查找，通过每次查找的值与期望值进行比对，从而实现每次排除一半答案，逐渐接近正确答案的查找方式。

1到100的数字，正常情况下需要猜100次能确保猜到正确答案。但是通过大与小这个比较信息，可以快速的找到答案。

1到100猜一个数字，最多要猜几次：

public class Main { public static void main(String[] args) { Main solution = new Main(); int maxGuess = 0; for(int i = 1; i <= 100; i++){ maxGuess = Math.max(maxGuess,solution.getGuessTime(i)); } System.out.println("最多需要猜："+maxGuess+"次"); } private int getGuessTime(int num){ int left = 1; int right = 100; int ans = 0; while(left <= right){ int mid = (right-left)/2+left; ++ans; if(mid == num) return ans; if(mid < num) left = mid+1; else right = mid-1; } return ans; }}

5.1 二分查找有啥用？

5.1.1 查缺失，查重复

查缺失：一组数字1到100按顺序排列，从中拿掉了一个，查拿掉的是谁；

public class Main { public static void main(String[] args) { Main solution = new Main(); Random r = new Random(); List list = new ArrayList<>(); for(int i = 1; i <= 100; i++){ list.add(i); } int rPos = r.nextInt(100); list.remove(rPos); System.out.println(list); System.out.println(solution.findLost(list)); } private int findLost(List list){ int leftIndex = 0; int rightIndex = 99; while(leftIndex

查重复：一组数字1到100按顺序排列，中间一个数字重复了两次，查重复的是谁。

import java.util.ArrayList;import java.util.List;import java.util.Random;public class Main { public static void main(String[] args) { Main solution = new Main(); Random r = new Random(); List list = new ArrayList<>(); for(int i = 1; i <= 100; i++){ list.add(i); } int rPos = r.nextInt(100)+1; list.add(rPos,rPos); System.out.println(list); System.out.println(rPos); System.out.println(solution.find(list)); } private int find(List list){ int leftIndex = 0; int rightIndex = 99; while(leftIndex

5.1.2 查找有多少个数字比当前数字小（大）

import java.util.*;public class Main { public static void main(String[] args) { Main solution = new Main(); Random r = new Random(); List list = Arrays.asList( 3,4, 15, 27, 30, 32, 40, 60, 72); Collections.sort(list); System.out.println(list); int curr = 31; System.out.println("比"+curr+"小的有："+solution.findSmallerCnt(curr,list)+"个"); System.out.println("比"+curr+"大的有："+solution.findLargerCnt(curr,list)+"个"); } private int findSmallerCnt(int num,List list){ if(list.size() == 0) return 0; if(num list.get(list.size()-1)) return n; int left = -1; int right = n-1; while(left < right){ int mid = (right-left+1)/2+left; if(list.get(mid) list){ if(list.size() == 0) return 0; int n = list.size(); if(num list.get(list.size()-1)) return 0; int left = 0; int right = n; while(left < right){ int mid = (right-left)/2+left; if(list.get(mid)<=num){ left = mid+1; }else{ right = mid; } } return n-right; }}

5.1.3 查看一个元素是否存在

public class Main { public static void main(String[] args) { Main solution = new Main(); Random r = new Random(); List list = Arrays.asList( 3,4, 15, 27, 30, 32, 40, 60, 72); Collections.sort(list); System.out.println(solution.hasNumber(list,60)); System.out.println(solution.hasNumber(list,7)); } private boolean hasNumber(List list, int num){ int n = list.size(); int left = 0; int right = n-1; while(left <= right){ int mid = (right-left)/2+left; if(list.get(mid)num){ right = mid-1; }else{ return true; } } return false; }}

5.1.4 二分猜答案

比如求 正整数 x 的开方的整数部分是几，比如 10 的开方是 3 点多，我们可以取 3。

public class Main { public static void main(String[] args) { Main solution = new Main(); System.out.println(solution.guessSqrt(102)); System.out.println(solution.guessSqrt(15)); } private int guessSqrt(int num){ int left = 1; int right = num; while(left

5.2 二分的优点和缺陷

5.2.1 优点

使用简单，容易理解。通过两个指针快速定出边界，排查查找范围。

降低时间复杂度，优化性能。二分查找的时间复杂度是 O(logn), 相比于直接按顺序查找的 O(n) 速度要快的多。

不需要额外空间。对于内存方面有优势。

5.2.2 缺点

查找指定元素时，要求数据必须有序。无序序列排序需要 O(nlogn) 时间复杂度，相比于顺序查找O(n)没有优势。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。