153. Find Minimum in Rotated Sorted Array

傳入一個經過迴轉n次的遞增數列nums，返回當中的最小值。

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

範例
Input: nums = [4,5,6,7,0,1,2]
Output: 0

所謂的迴轉1次就是數列中元素的位置從nums[n]變為nums[n+1]，而數列最右側移到nums[0]。

這題要求是O(log n)，因此不允許逐筆來比大小的O(n)，一定要從跳號的方式來思考。

先看範例來觀察規律

[4,5,6,7,0,1,2]

抓頭、尾還有當中間隨機一點「A」來觀察；由左到右移動「A」能發現以下規律

1.  A 大於頭、尾，表示還沒有跨過最小值，因此最小值在靠 A 右側的子數列。
2.  A 小於頭、尾，表示已經跨過最小值，因此最小值在靠 A 左側的子數列。
3.  A 只有一種情況會在頭、尾之間，如下圖；就是頭是最小值，尾是最大值。

[0,1,2,4,5,6,7]     

我們依循這個規則，對得到的子數列重複作業，直到將數列收緊為止，即是我們要的答案了

	public int findMin(int[] nums) {
		
		int first = 0;
		int last = nums.length - 1;

		int ans = Math.min(nums[last], nums[first]);
		while (last - first > 1) {
			// 取本次數列的中間值為「A」
			int mid = (first + last) / 2;
			
			//「A」介於頭、尾間，表示首項已是最小值
			if (nums[mid] >= nums[first] && nums[mid] <= nums[last]) {
				return nums[first];
			}

			if (nums[mid] < ans) {
				//「A」小於頭、尾
				last = mid;
				ans = nums[mid];
			} else {
				//「A」大於頭、尾
				first = mid;
			}
		}
		return ans;
	}