LeetCode 153 Find Minimum in Rotated Sorted Array

思路

二分法。寻找第一个<=last number的点（不能找第一个</<=first number，可以举例子得到，<: 12345 = o x x x x;<=:45123 = x o x x x）。比如：
4 5 1 2 3 || 1 2 3 4 5
o o x x x || x x x x x

复杂度

时间复杂度O(logn)
空间复杂度O(logn)

代码

public class Solution {
    /*** @param nums: a rotated sorted array* @return: the minimum number in the array*/public int findMin(int[] nums) {
    // write your code hereif (nums.length == 0) {
    return -1;}int start = 0, end = nums.length - 1;while (start + 1 < end) {
    int mid = start + (end - start) / 2;if (nums[mid] > nums[end]) {
    start = mid;} else if (nums[mid] <= nums[end]) {
    end = mid;}}if (nums[start] <= nums[nums.length - 1]) {
    return nums[start];}if (nums[end] <= nums[nums.length - 1]) {
    return nums[end];}return -1;}
}

Follow-up

如果允许数组中有重复的数字，那么二分不可用，因为可能会是[1,1,1,…,1]中有一个0, 复杂度只能是O(n)