【手绘漫画】面试必考之二分查找（解题模板和深度剖析），上回

1、前言

之所以断更了一天，就是因为上次说的这个二分查找，，，看的我心态多没了，之后就这阶段就一直刷二分查找了！！！

这是一个很经典的题目，【二分查找】问题。

初步上手二分查找的时候，总觉得很简单，但是真的简单嘛？？？

其实并不简单！！！

可以看看一些大佬关于二分查找法的论述：

• 算法和程序设计技术的先驱 Donald Ervin Knuth（中文名：高德纳），也就是发明 KMP(Knuth-Morris-Pratt) 算法的那位，是怎么说的：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky... 这句话我看到的最佳的翻译是：思路很简单，细节是魔鬼。同样是高德纳先生，在其著作《计算机程序设计的艺术 第 3 卷：排序和查找》中指出：二分查找法的思想在 1946 年就被提出来了。但是第 1 个没有 Bug 的二分查找法在 1962 年才出现。
• 另一位大佬，是《编程珠玑》的作者 Jon Bentley，他是这么说的：When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases.翻译：当 JonBentley 把二分查找作为专业程序员课程中的一个问题时，他发现百分之九十的人在花了几个小时的时间研究之后，没有提供正确的解决方案，主要是因为错误的实现无法正确运行，或者是不能很好地判断边界条件。

看到了吧，基本上十人九错，，，

什么是二分查找？

二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分查找中使用的术语：

• 目标 Target —— 你要查找的值；
• 索引 Index —— 你要查找的当前位置；
• 左、右指示符 Left，Right —— 我们用来维持查找空间的指标；
• 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引；

代码大体都没啥问题，就是边界条件，比方说：while 的不等号是否应该带等号，right 和 left 是不是要让 mid 加一等等。

2、代码

模板：

// Cint search(int* nums, int numsSize, int target) {//	  数组一般是升序的，如果最后一个元素小于target，则找不到//    if (nums[numsSize - 1] < target) {//        return -1;//    }
    int left = 0;    int right = numsSize - 1;
    while (left <= right) {    	// int mid = (left + right) / 2;    	// int mid = left + (right - left) / 2;    	// 最好这么写，不然会内存溢出        int mid = (left + right) >>> 1 ;        // 等于的情况最简单，首先判断，没准一下就中了！        if (nums[mid] == target) {            return mid;        }        else if (nums[mid] < target) {            // 左边界更新为 mid + 1            left = mid + 1;        }        else {            // 右边界更新为 mid - 1            right = mid - 1;        }    }    return -1;}

3、代码

什么时候使用二分查找？

其实如果题目告诉你 排序数组，其实就是在【疯狂暗示】你用二分查找。

那么有哪些地方需要注意呢？

1. 为什么 while 循环的条件中是 <=，而不是 < ？

初始化 right 的赋值是 nums.length - 1，相当于区间 [left, right]，

什么时候停止搜索呢？

当然，找到了 target 时终止，或者 while 条件不符时：

找到时：

if(nums[mid] == target)		return mid;

但如果没找到：

就需要 while 循环终止，while(left <= right) 的终止条件是 left == right + 1。

1. 中位数怎么写？

其实很多同学是这么写的，int mid = (left + right) / 2，这行代码其实是有问题的，在 left 和 right 都比较大的时候，left + right 两个 int 很有可能超过 int 类型的最大值，即整型溢出。

为了避免这个问题，又出现了第二种写法：int mid = left + (right - left) / 2，事实上，这种写法在 right 很大、 left 是负数且很小的时候，right - left 也有可能超过 int 类型能表示的最大值，只不过溢出的可能性很小。

更好的写法是：int mid = (left + right) >> 1。

但是这种写法存在局限，等我完成LeetCode探索之后，再讲下一篇。