前言
今天来杭州参加百阿
培训，住在4星级的旅馆，加上快一月底了我都没有几篇博客产出，所以准备开始水LeetCode题目了，这里介绍一个二分查找的应用。
题目
Suppose a sorted array 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.
思路
O(n)
看到这道题目，我的第一感觉是二分法，但是如何进行二分，却没有明确的思路出现在我的脑海中（悲剧，最近
Android
系统搞多了，算法能力急剧下降）。但是，如果这是面试的一道题目，你不可能因为你不会二分就放弃了这道题目的解答，因此我尝试通过增加一点时间复杂度来解决这到题目，思路如下： 首先，定义一个boolean值的标志位flag，初始为false，循环遍历找到了最小元素就置为true。定义数组num循环的起点begin为0，终点end为num.length - 1，循环的条件是begin < end。循环体内部，我们考虑，如果num[begin] > num[end]，说明了数组发生了旋转，这时我们只需要将begin+1，继续比较，直到找到第一个小于end的值即为最小值。如果num[begin] < num[end]，说明数组没有发生循环，那最小值自然为num[begin]。 有了思路，代码自然产出，AC代码如下所示：
public class FindMinimumInRotatedSortedArray {
public int findMin(int[] num) {
if (num.length == 1) {
return num[0];
}
int begin = 0, end = num.length - 1;
boolean flag = false;
while (begin < end) {
if (num[begin] > num[end]) {
begin += 1;
} else {
flag = true;
break;
}
}
if (flag) {
return num[begin];
} else {
return num[end];
}
}
} 虽然代码AC了，但是对于一个追求效率的人来说，这种代码显然是不满足要求的，因为该代码的时间负责度为O(n)。如果采用二分查找算法，则时间复杂度为O(logn)，所以我们必须考虑对代码的优化。
O(logn)
这个负责度我们必然要考虑二分算法了。百阿期间和一个小伙伴睡前讨论得出了该解决方案。假设数组名为num，当我们确认了起点begin，终点end后，那么mid所代表值的大小只有两种可能： num[begin] < num[mid]。在一个被旋转的数组中，当num[begin] < num[mid]时，那最小值min可能为num[begin]或者位于区间[mid + 1, end] 之间。num[mid] < num[end]。这种情况下，最小值min可能为num[mid]或者为区间[begin, mid - 1]中的值。 单说结论比较抽象，为了方便理解，我给出下图。同时提醒大家，做ACM题目找不到思路的时候，尝试一下画图来理清思路。
当然，更好的方式是在演算纸上画图，思路有了，代码很自然就写出来了。AC代码如下：
public class FindMinimumInRotatedSortedArray {
public int findMin(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
int left = 0, right = num.length - 1, min = num[left], mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (mid == left || mid == right) {
break;
}
if (num[left] < num[mid]) {
min = Math.min(min, num[left]);
left = mid + 1;
} else if (num[mid] < num[right]) {
min = Math.min(min, num[mid]);
right = mid - 1;
}
}
min = Math.min(num[left], min);
min = Math.min(num[right], min);
return min;
}
}