153.Find-Minimum-in-Rotated-Sorted-Array

153. Find Minimum in Rotated Sorted Array

题目地址

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

题目描述

Suppose a sorted array 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.

Example
Example 1:

Input：[4, 5, 6, 7, 0, 1, 2]
Output：0
Explanation：
The minimum value in an array is 0.
Example 2:

Input：[2,1]
Output：1
Explanation：
The minimum value in an array is 1.

代码

Approach #1 Binary Search

public class Solution {
    public int findMin(int[] nums) {
    if (nums.length == 1) return nums[0];

    int left = 0, right = nums.length - 1;
    if (nmus[right] > nums[0])    return nums[0];

    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid - 1] > nums[mid]) {
        return nums[mid];
      }

      if (nums[mid] > nums[0]) { // 和 nums[0] 比较
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }
}

Approach 2:

class Solution {
  public int findMin(int[] nums) {
    if (nums == null || nums.length == 0)    return -1;

    int start = 0, end = nums.length - 1;
    int target = nums[nums.length - 1]; // 和最后一个数字比较

    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (nums[mid] <= target) {
        end = min;
      } else {
        start = mid;
      }
    }

    return Math.min(nums[start], nums[end]);
  }
}