「二分查找」之我见！今天刷一道leetcode算法！
来自:码农田小齐
算法将是我今后更新的重点，因为我个人非常喜欢。。而且面试考它啊！有人说刷题没有用，但是你做了题就能感受到 coding 能力的提升和对语言熟悉度的提升。新的一年，每日一题，我们一起进步一起NB！
今天第一题选了我最喜欢的也是折磨了我很久的但并不算难的题目，最终是因为在 GS 电面中被问到了，我才痛下决心把这类题目一网打尽。
先来看最基本版的题目：Leetcode 153题
题干是给了一个【本来排好序了的 且为升序】的数组，然后又在某个不知道的位置旋转了一下，所谓旋转，就是把前面那堆数移到后面来了，求新数组的最小值。比如：
原 array：[0, 1, 2, 4, 5, 6, 7]
rotate 之后就是：[4, 5, 6, 7, 0, 1, 2]
输出：最小值 0
解法一：
Brute Force 暴力解法就是每个数都过一遍，然后用一个变量记录我们见到过的最小值并随时更新。（这个应该都会吧，不会的话可以后台留言告诉我。。请让我看到你。。）
Time complexity = O(n)，因为每个数都过了一遍；
Space complexity = O(1)，因为只用了有限几个变量。
解法二：
在 O(n) 的基础上我们还想优化，那方向是 O(logn)，再想想查找类算法的很容易想到了 binary search。
binary search 的做法就是每轮排除一半，留下另一半是包含正确答案的，再不断缩小范围，把答案找出来。那么解决的关键就在于如何杀掉这一半而不能把答案误杀了。中文叫二分查找，我认为翻译的挺好的，因为只有一次分两份，去掉一份，才能保证时间复杂度是 O(logn)。（此处不懂可以后台留言给我，我会根据反馈在之后的文章补充。）
那么二分查找题目的考点就在于如何排除掉这一半了，一般是通过比较中间的数和左右两端或者目标值的关系，但没有统一的规律，否则还考啥？只能多见多去领悟其精髓，我会在更新完所有 binary search 的题目之后做个总结。
就这一题来说，我们比较 array[mid] 和 array[left] or array[right] 的大小关系，哪边都行。
方法一、先看和右边的比较
-
如果 array[mid] > array[right]，如下图例子，7 比 2 要大，这是不正常的（不升序）的，说明最小值在右边，所以排除左边以及 mid（array[mid] 已经比 array[right] 大了，不可能为最小值），所以 -
left = mid + 1；
-
如果 array[mid] < array[right]（没有=，因为没有duplicates），说明右边是 sorted 的，说明 最小值在左边甚至可能就是 mid 本身，所以 -
所以 right = mid。
-
while终止条件是 left == right 的时候，此时 mid = left = right， 返回nums[left] = nums[right] 都行。
// Javaclass Solution{public int findMid(int[] nums) {if(nums == null || nums.length == 0) {return -1; // discuss with interviewer}int left = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left)/2;if(nums[mid] > nums[right]) {left = mid + 1;} else {right = mid;}}return nums[left];}}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.Memory Usage: 38.5 MB, less than 79.54% of Java online submissions for Find Minimum in Rotated Sorted Array.*/
方法二、再看和左边比较
-
如果 array[mid] >= array[left]（这里可能=，因为 mid 可能就是 left；而 mid 不可能是 right，因为 Java 向0取整且如果 left = right 就跳出循环了），那么 左边是 sorted 的，最小值在右边（题目说一定 rotated 了），所以 left = mid + 1，但有两点要注意： 注意 ⚠️ ： 最小值有可能就是 left，虽然最初数组是 rotate 了，但是在减半之后有可能就是完整 sorted 的 所以此方法还要加一步：最开始先判断是否是sorted的，即array[left] vs array[right]
-
如果 array[mid] < array[left]，那么右边是 sorted 的，最小值在左边甚至是 mid 本身，所以 right = mid。 -
while loop 条件同上
// Javaclass Solution {public int findMid(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right) {if(nums[left] < nums[right]) { //⚠️return nums[left];}int mid = left + (right - left)/2;if(nums[mid] >= nums[left]) { //⚠️left = mid + 1;} else {right = mid;}}return nums[left];}}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.Memory Usage: 38.6 MB, less than 77.27% of Java online submissions for Find Minimum in Rotated Sorted Array.*/
这题说完了。
Follow up 是154题，可能有 duplicates 的情况。大家可以稍作思考再往下看。
基本思路和上一题一样，但是 [3, 3, 1, 3] 不work，因为当 mid = right 时，无法判断最小值到底在哪边，所以只能一步步走，worst case O(n) 避免不了。
// Javaclass Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left)/2;if(nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] == nums[right]) {right --;} else {right = mid;}}return nums[left];}}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array II.Memory Usage: 41.8 MB, less than 6.25% of Java online submissions for Find Minimum in Rotated Sorted Array II.*/
以上就是 rotate array 中找最小值的完整方法了，明天我们来看在 rotate array 中找一个特定目标值的题目，这题有很多方法，我会分享我认为觉得最好的一种，会对 binary search 的理解更加深刻。
题目：Leetcode 33 & 81
特别推荐一个分享架构+算法的优质内容，还没关注的小伙伴，可以长按关注一下：
长按订阅更多精彩▼
如有收获，点个在看，诚挚感谢