说起经典面试题，我最记忆犹新的是我的第一次技术面试——2008年我申请研究生时被问到的这道题。题目描述是这样的：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.
方法一
俗话说的好，没方法不如烂方法。如果把这道题给一个大一新生，想必他一定会说：so easy，循环一圈挨个比一下不就好了。没错，如此暴力搜索确实可以解决问题，Java 代码也很直截了当：
不要小看如此直接的代码，这里面也是有不少坑可以掉的。同学们面试时最容易忽视的就sanity check，也就是这段代码第1-3行的部分。不然的话，如果输入数组null，那么程序在运行时会抛出NullPointerException。接下来嘛，十有八九面试官也会向同学抛出NullOfferException了。
另一个初学者经常容易混淆的概念是nums == null和nums.length == 0的区别。其实如果拿现实生活做类比的话，前者就好比说我没带钱包，而后者则是我带了钱包但里面没有钱。此外，这两个检查的先后顺序也是很重要的，null check必须在前面。这是因为在 Java 语言里，逻辑表达式是按照从左到右的顺序遵循 short circuit求值的。在这个表达式里如果逻辑或（||）的前半段nums == null为true，那么后半段无论为何值整个表达式的值也一定为true，于是Java 在这种情况下根本就不会试图去执行nums.length。然而如果我们反过来把它写成了nums.length == 0 || nums == null，那么当nums == null 的时候还是会抛出NullPointerException。
说了这么多，我们返回头来看这个算法本身。它对是对，然而并不优。由于它要把数组里每个元素都和 target 比较一遍，时间复杂度是 O(n) 的。归根结底，它并没有利用到数组已经几乎排好序的条件。那么有什么办法利用这个条件来优化呢？
退化版问题一：Search in Sorted Array
我们先从简单问题来考虑，假设这个数组并没有被 rotate 过，那么这道题就变成一道经典的在有序数组里查找一个元素的问题，其方法自然是 binary search。
Binary search算法的核心要义在于我们每次可以排除掉数组里一半的元素，在剩余的另一半里继续寻找 target，并不断重复这个过程。由于数组已经按照升序排列，于是我们只需将数组最中间的元素和target进行比较，如果相等则说明刚好找到，不然如果数组的中位元素小于 target则继续在后半个数组里寻找，反之则在前半个数组里寻找。整个过程的结束条件是要么我们找到了target（返回其 index），要么数组里的所有元素都被已经排除掉了（返回 -1）。对应的Java代码如下：
这段代码里也有几个细节值得注意。首先第1-3行就不必说了，希望看到这里sanity check已经融化到同学们的血液中了。第6行的循环为什么一定要left <= right？如果写成left < right行不行？同学们在面试的时候也要注意，写出正确代码只是最基本的要求，在此之上还要能够回答面试官的各种challenges。此时我们可以举一个最简单的例子来思考，假设数组只有一个元素，那么left = right = 数组唯一的元素。如果循环条件写成left < right的话，这个循环根本就进不去，直接就返回 -1了。接下来第11行，为什么这里一定要left = mid + 1 而不是left = mid？我们继续举一个最简单的例子。假如数组只有唯一一个元素 nums = {5}，而我们的 target = 7。第一轮 left = right = mid = 0（都指向数组唯一的元素 nums[0] = 5），如果第11行这里不加一的话，则下一轮循环依然是 left = right = 0，于是就死循环了。可见这里加一是必须的。同理，第13行的减一也是必须的。除此之外，第7行之所以不直接写成 mid = (left + right) / 2 是为了防止两个大整数相加溢出。这也算是面试时的一个小细节。Binary search 由于每次可以排除掉数组里一半的元素，其时间复杂度只有 O(log n)，远远好于方法一的暴力搜索。然而我们只解决了退化版的问题。对于 rotate 过的有序数组又该怎么办呢？
退化版问题二：Find Minimum in Rotated Sorted Array
在回到最开始的问题之前，我们再来看一个比刚才稍微进化一点（但依然是原题退化版）的问题。问题描述如下：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.You may assume no duplicate exists in the array.
这道题和原题的唯一区别在于我们不需要找任意 target，而只需要找到数组里的最小元素。数组里的最小元素出现在哪里呢？如果是严格升序的数组，其最小值一定是第一个元素。对于 rotate 过的数组，其最小值一定出现在该 rotation 的唯一拐点。如下图所示：
原数组：
新数组：
除此之外，我们注意到严格升序的数组一定满足其最左端元素的值小于最右端元素的值，而 rotate 过的数组一定是最左端元素的值大于最右端元素的值。由于数组的最小值（拐点）是唯一的，我们可以按照如下思路进行 binary search：如果一段数组已经是严格升序，那么直接返回其最左端元素即可。不然我们可以把数组分为两半，其中一半一定是严格升序的，而另一半依然是一个 rotated sorted array，且其中包含原数组的最小值（拐点）。这样我们可以排除掉严格升序的那一半，而在另一半里继续找最小值。具体来讲，假设 binary search 的左端点为 left，右端点为 right，中间点为 mid。首先，如果 nums[left] < nums[right] 则说明数组已经严格升序，直接返回 nums[left] 就是最小元素。不然如果 nums[mid] > nums[right] 则说明右半段数组是 rotate 过的（且 mid 不可能是最小元素），最小值一定出现在 nums[mid + 1] ...nums[right] 当中。否则说明右半段数组是严格升序的，最小值一定出现在 nums[left] ...nums[mid] 当中（注意这里并不能排除掉 mid 本身）。如此循环，直到搜索范围只剩下一个元素，就是我们要找的最小值。对应的 Java 代码如下：
同学们可以比较一下这道题与上一题的经典 binary search 代码的异同，并仿照上一题的方法思考一下第6行的循环条件写成 left <= right 行不行，第12行写成 left = mid 行不行，第14行写成 right = mid - 1 行不行。这里不再赘述。这道题我们也是每次排除掉数组里的一半元素，所以时间复杂度还是O(log n)。
方法二
在有了前面两个退化版问题铺垫下，最开始的问题也就迎刃而解了。我们只需要首先用退化版问题二的方法找到数组的拐点，然后把数组 rotate 回严格升序的，再用退化版问题一的方法来寻找 target 即可。Java 代码如下：
两次binary search的时间复杂度都是O(log n)，总的时间复杂度为O(log n + log n) = O(log n)，比方法一的 O(n) 好太多了。然而代码写成这样未免太啰嗦了。有没有办法只用一次Binary Search就一步到位呢？必须的。
方法三
其实一步到位的方法还是利用了经典 binary search 的思想，每次将数组分为两半，将最中间的元素和 target 进行比较，如果相等则说明刚好找到。唯一的区别在于如果不相等时接下来该继续搜索哪一半。这时就要将退化版问题一和退化版问题二的思路结合起来。既然两半当中一定有一半是严格升序的，我们只需要判断 target 是不是在这一半里面即可——是则搜索这一半，不是则搜索另一半。Java 代码如下：
时间复杂度还是 O(log n)，然而代码却简洁了不少。
通过这道题，希望同学们在学习 binary search 的时候不要死记硬背，而是深入理解并融会贯通，遇到新题能够化繁为简。
汤老师
来offer王牌讲师之一。清华大学计算机系信息学竞赛保送生，美国哥伦比亚大学计算机系软件系统实验室博士生，曾在 OSDI、CACM 等操作系统领域最顶级学术会议和期刊上发表多篇论文。曾参与 Chrome 和 Google Cloud Platform 的研发工作。
图片来自网络，版权属于原作者
