RNG输了，但我们不能输

前言

RNG输了，输在了轻敌，没有把G2当人看，随随便便bp,就是告诉你，我4保1奥巴马我也可以赢，结果啪啪啪打脸。

我们从这件事中得到的教训就是不要膨胀，不管面试中出的题多么简单，都要去认真对待，切不可轻敌，留下遗憾啊！

在我面过的公司里面，去哪儿、秒针、猎豹、作业帮等公司都考察了二分查找，去哪儿在实习和秋招都考察了二分查找。

对于一个简简单单的二分查找，你真的能完全写对吗？越是面试中考察简单的东西，越需要花点心思去搞明白~

概念介绍

什么是二分查找

维基百科

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

案例1

题目

去哪儿/一点咨讯 手写代码题：

对于一个排序数组，无重复数字，给定一个数target,如果这个数target存在，那么返回它出现的下标，如果不存在返回-1。

错误示例

一些朋友看到这题，心里道：“乔兄，这也太简单了吧！”。完全有把这道理放在眼里，十分膨胀，话语刚落，已经开始在编辑器花了5分钟刷刷地写了出来。

“乔兄，我写完了，你看！”

代码：

1. class Solution {

2.    public int search(int[] nums, int target) {

3.        int left = 0;

4.        int right = nums.length - 1;

5.        if(nums.length == 0)

6.            return -1;

7.        while(left <= right)

8.        {

9.            int mid = (left + right) / 2;//标记

10.            if(nums[mid] > target)

11.                right = mid - 1;

12.            else if(nums[mid] < target)

13.                left = mid + 1;

14.            else{

15.                return mid;

16.            }

17.        }

18.        return -1;

19.    }

20. }

上述代码，在数据量比较低的情况下是没有问题的，但是当数据量非常大，比如说nums这个数目的长度是int的最大值2147483647，而我们要找的数刚好在数组的右半部分，那么left大于1/2（int 最大值）,right的值大于1/2（int的最大值），此刻在求mid = (left + right)/2的时候就会产生溢出，大于整数的最大值，进而产生错误！！！

如何改进

• long mid = (left + right) / 2; //将mid的值的类型设置为long;

• int mid = left + (right-left)/2;//推荐这种写法，这种写法的意思就是用右边界的值减去左边界的值，得到差值，然后左边界的值加上差值的1/2就是mid值~

一道简单的二分查找，但可千万别小看，面试官越是问的简单的手写代码题，越要看仔细了，越是简单，越有可能阴沟里翻船！

案例2

题目

百度一面面试题：

求二叉树中的最小深度。

示例

深度是按照一层一层来进行计数的，根结点A的深度就是1，再往下一层（B，C所在的层）的话深度就是2。

下图中的二叉树的最小深度(D,E,F,G所在的层)就是3，A代表的是根结点，G,I,E,F,G代表的是叶子节点。

下图中的二叉树的最小深度(B,C所在的层）就是2，A代表根结点，C，E，G，I代表的是叶子节点。

错误示范

当时我一看这题感觉是送分题啊，我拿起笔很快地就写了出来。

思路：递归的思路，就是每次找每个节点的最小深度，最开始是去寻找叶子节点的最小深度，然后叶子节点的最小深度知道了以后，就得到了叶子节点的父亲节点的最小深度，这样一层层回溯的过程就把每个节点所代表的二叉树的最小深度知道了，最后根结点代表的二叉树的最小深度就知道了。

代码：

1. public class Solution {

2.    public int minDepth(TreeNode root) {

3.        if(root == null) return 0;

4.        int left = minDepth(root.left);

5.        int right = minDepth(root.right);

6.        if(left == 0 || right == 0)

7.            return left+right+1;

8.        //左子树或者右子树有一个为空

9.        //left为0直接返回右子树的最小深度+1

10.        else

11.            return Math.min(left,right)+1;

12.        //左右子树都不为空，返回高度较小的

13.    }

14. }

写完以后，我觉得没什么问题，就让百度的面试官去看了，面试官看了以后说，“写的挺好，但是如果当这个树的节点数目非常大的时候，是不是效率上会慢一些，有没有什么改进方法？”

我恍然大悟，我说咋出这么简单的题，原来是考察在大数据的情况下的最优解，怪就怪在我自我膨胀了，没认真对待面试官出的这道题。

如何改进

我上述的代码是在小数据的情况下，是OK的，在大数据的情况下，需要遍历的时候，按照层次遍历的思路，找到第一个叶子节点，然后就结束遍历了，无需再进行遍历，因为题目是最小深度，所以已经找到了，就结束返回结果就完事了，还遍历干啥？

代码：

1. class Solution {

2.    public int minDepth(TreeNode root) {

3.        int level = 1;//深度

4.        int toBePrinted = 1;

5.        //接下来要打印的节点个数

6.        int nextLevelNumber = 0;

7.        //下一层节点的数目

8.        if(root == null)

9.            return 0;

10.        Queue<TreeNode> queue

11.        = new LinkedList<>();

12.        //用一个队列存节点

13.        queue.add(root);

14.        while(!queue.isEmpty())

15.        {

16.            TreeNode temp = queue.poll();

17.            toBePrinted--;

18.            if(temp.left == null

19.              && temp.right == null)

20.            {//找到叶子节点

21.             //就返回当前的层数就是最小深度

22.                return level;

23.            }

24.            if(temp.left != null)

25.            {

26.                queue.add(temp.left);

27.                nextLevelNumber++;

28.            }

29.            if(temp.right != null)

30.            {

31.                queue.add(temp.right);

32.                nextLevelNumber++;

33.            }

34.            if(toBePrinted == 0)

35.            {//上一层节点遍历完了

36.             //层数加1，并将计数的

37.             //nextLevelNumber置位0

38.             //toBePrinted 是下一层

39.             //要打印的节点数目

40.                toBePrinted = nextLevelNumber;

41.                nextLevelNumber = 0;

42.                level++;

43.            }

44.        }

45.        return level;

46.    }

47. }

结束语

面试中遇到的任何的问题，都不可以掉以轻心，不要膨胀，稳扎稳打，持之以恒，不懈努力，那么相信offer在向你招手。

RNG输了，我们不能输！加油！

END

推荐阅读

三位斩获百度C++后台开发offer大佬的口述分享！！！

我的2019校招

极有可能是你朋友圈最全的3T编程资料分享！！！