leetcode解题: Find Minimum in Rotated Sorted Array (153)

发表于 | 分类于

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

You may assume no duplicate exists in the array.

这也是一题经典的binary search的题目。 难点在于怎么判断最小值是在mid的左面还是右面，以此来缩小范围。
当搜索的范围[start, end]确定了之后，mid的取值可以有几种情况

  • start < end, 那么最小值在start和mid之间
  • start > end, 那么最小值的位置取决于mid和start，end的关系
    • 如果mid < end, 那么最小值一定在start和mid之间
    • 如果mid > end, 那么pivot点一定在mid和end之间。
      按照这个思路写程序就很简单了。
      C++
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      class Solution {
      public:
          int findMin(vector<int>& nums) {
             if (nums.size() == 0) {
      			return -1;
      		}
      		int start = 0, end = nums.size() - 1;
      		while (start + 1 < end) {
      			int mid = start + (end - start) / 2;
      			if (nums[start] < nums[end]) {
      				end = mid;
      			} else {
      				if (nums[mid] < nums[end]) {
      					end = mid;
      				} else {
      					start = mid;
      				}
      			}
      		}
      		if (nums[start] < nums[end]) {
      			return nums[start];
      		} else {
      			return nums[end];
      		} 
          }
      };

Java

1