LeetCode Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

思路分析：这题主要考察二分查找，在Rotated Sorted Array中找最小和Search in Rotated Sorted Array类似，只不过此时需要不断把最左边的元素A[l]与A[m]比较

1. 如果A[m] < A[l] 那么应该在左边找，更新右边的边界right；

2.如果A[m] > A[l] 那么应该在右边找，更新左边的边界left；

3.如果A[m]= A[l] ,l++;

上述规律可以通过举例子很快发现，这样可以每次减少一半元素，得到O（logN）的算法。注意这题A[m] = A[l] 也有可能发生，虽然没有重复元素，但是m和l可能指向同一个元素，比如当这个数组只有两个元素的时候。如果A[m]= A[l] ,可以执行l++;丢掉一个“冗余元素”也不会丢掉最小值。对于Rotated Sorted Array中有冗余值的情况可以参考本题的扩展Find Minimum in Rotated Sorted Array II。

AC Code

public class Solution {public int findMin(int[] nums) {int n = nums.length;int l = 0;int r = n-1;int min = nums[0];while(l < r){int m = l + (r-l) / 2;if(nums[m] < nums[l]) {min = Math.min(nums[m], min);r = m;} else if(nums[m] > nums[l]){min = Math.min(nums[l], min);l = m;} else {l++;}}min = Math.min(nums[l], min);min = Math.min(nums[r], min);return min;}}

如果觉得《LeetCode Find Minimum in Rotated Sorted Array》对你有帮助，请点赞、收藏，并留下你的观点哦！