33. Search in Rotated Sorted Array

傳入一個經過迴轉n次的遞增數列nums，和整數target，返回target在nums中的位置，若不存在則回傳 -1。

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

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

迴轉的意思可以參考這邊。
這題一直想不出好的解法，只好把所有的Case都走一遍。

把數列寫為代數[a,....,c,..,b]，中間任取一點為 c ，

a , b 只會有以下兩種狀況

a < b  //數列沒有迴轉
a > b  //數列有迴轉

這時我們再依序討論有迴轉與沒迴轉內的Case。沒迴轉的情況因為是遞增數列，因此只要比較target和c的大小即可知道target是落在哪一邊子數列。

       ┌ target < c  //目標比c還小，會落在左側子數列
a < b  ┴ target > c  //目標比c還大，會落在右側子數列
        
a > b  

再來考慮有迴轉的狀況，有迴轉的狀況雖無法直接比較，但我們可以從 c 知道迴轉是發生於左右子數列的哪一邊。

       ┌ target < c  
a < b  ┴ target > c  
        
a > b  ┬ c < a and b //c比頭尾還小，表示右側為順向
       └ c > a and b //c比頭尾還大，表示左側為順向

我們再拿「順項」那邊的子數列來確認target是否被夾在內，因為非順項是無法得知目標是否被夾在內的。

       ┌ target < c  
a < b  ┴ target > c  
                     ┌ c < target < b  //目標落在此
a > b  ┬ c < a and b ┴                 //否則落在[a,c]子數列
       ｜
       └ c > a and b ┬ a < target < c  //目標落在此
                     └                 //否則落在[b,c]子數列

至此所有的情況都被我們考慮進去了，只需要用同樣的方法一直loop取得的子數列，就能夾住目標，若到已經縮到最小的數列卻還沒找到目標，表示不存在，回傳 -1 即可。

	public int search(int[] nums, int target) {

		int start = 0;
		int end = nums.length - 1;

		while (end - start > 1) {

			// 若頭尾等於目標，直接中止
			if (nums[start] == target || nums[end] == target) {
				break;
			}

			int mid = (start + end) / 2;

			if (nums[start] < nums[end]) {
				// 未轉向
				if (nums[mid] > target) {
					// 目標於左側子數列
					end = mid;
				} else {
					// 目標於右側子數列
					start = mid;
				}
			} else {
				// 有轉向
				if (nums[mid] < Math.min(nums[start], nums[end])) {
					// 迴轉在左，因此我們使用右側的子數列來比較大小
					if (nums[mid] < target && target < nums[end]) {
						// 目標落於右側子數列
						start = mid;
					} else {
						// 目標落於左側子數列
						end = mid;
					}

				} else {
					// 迴轉在右，因此我們使用左側的子數列來比較大小
					if (nums[start] < target && target < nums[mid]) {
						// 目標落於左側子數列
						end = mid;
					} else {
						// 目標落於右側子數列
						start = mid;
					}

				}
			}
		}

		// 頭尾等於目標回傳數列的位置
		if (nums[start] == target) {
			return start;
		}
		if (nums[end] == target) {
			return end;
		}

		// 查無目標
		return -1;
	}