3.12 Find Minimum in Rotated Sorted Array寻找旋转排序数组中的最小值

http://www.lintcode.com/en/problem/find-minimum-in-rotated-sorted-array/

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

Find Minimum in Rotated Sorted Array (leetcodelintcode)

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

Notice
You may assume no duplicate exists in the array.

Example
Given [4, 5, 6, 7, 0, 1, 2] return 0

解题思路

参考题目 Search in Rotated Sorted Array ，在旋转数组中寻找最小值，可能出现以下三种情况：

其中，在情况（a）和情况（c），end 都需要往中间移动，而在情况（b），start 需要往中间移动，由此可以得出我们的解法如下。

算法复杂度

• 时间复杂度： O(logn) 。

Java 实现

public
class
Solution
{

/**
     * 
@param
 nums: a rotated sorted array
     * 
@return
: the minimum number in the array
     */
public
int
findMin
(
int
[] nums)
{

if
 (nums == 
null
 || 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]) {
                end = mid;
            } 
else
  {
                start = mid;
            } 
        }

if
 (nums[start] 
<
 nums[end]) {

return
 nums[start];
        }

return
 nums[end];
    }
}