【題目描述】

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.

Notice

You may assume no duplicate exists in the array.

假設一個旋轉排序的數(shù)組其起始位置是未知的（比如0 1 2 4 5 6 7可能變成是4 5 6 7 0 1 2）。

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

注：你可以假設數(shù)組中不存在重復的元素。

【題目鏈接】

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

【題目解析】

首先要判斷這個有序數(shù)組是否旋轉了，通過比較第一個和最后一個數(shù)的大小，如果第一個數(shù)小，則沒有旋轉，直接返回這個數(shù)。如果第一個數(shù)大，就要進一步搜索。

我們定義left和right兩個指針分別指向開頭和結尾，還要找到中間那個數(shù)，然后和left指的數(shù)比較，如果中間的數(shù)大，則繼續(xù)二分查找右半段數(shù)組，反之查找左半段。終止條件是當左右兩個指針相鄰，返回小的那個。

【參考答案】

www.jiuzhang.com/solutions/find-minimum-in-rotated-sorted-array/