《leetcode-go》在轉動過的有序數組中尋找目标值

給出一個轉動過的有序數組，你事先不知道該數組轉動了多少

(例如,0 1 2 4 5 6 7可能變為4 5 6 7 0 1 2).

在數組中搜尋給出的目标值，如果能在數組中找到，傳回它的索引，否則傳回-1。

假設數組中不存在重複項。

思路：轉動之後二分之後一半是有序的，另一半繼續二分有一半是有序的，這樣就是一種變相的二分查找。

package main

/**
  * 
  * @param A int整型一維數組 
  * @param target int整型 
  * @return int整型
*/
func search( A []int ,  target int ) int {
    // write code here
    right := len(A) - 1
	left := 0
	for left <= right {
		mid := (left + right) / 2
		if A[mid] == target {
			//找前後的位置
			return mid
		}
		//通過判斷他是否是有順序的
		if A[left] <= A[mid] {
			//如果左邊是有順序的
			if target < A[mid] && target >= A[left] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			//如果右邊是有順序的
			if target > A[mid] && target <= A[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}