假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

（ 例如，數組 ［0，1，2，4，5，6，7］ 可能變為 ［4，5，6，7，0，1，2］ ）。

搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設數組中不存在重復的元素。

你的算法時間復雜度必須是 O（log n） 級別。

示例 1：

輸入： nums = ［4，5，6，7，0，1，2］， target = 0

輸出： 4

示例 2：

輸入： nums = ［4，5，6，7，0，1，2］， target = 3

輸出： -1

解法1：如果是 left 《 right，就是有序數組，用二分來處理；否則，target可能落在 left~mid和mid~right兩個區間內。

如果 left 《= target 《=mid 或者 left 》 mid 并且 target 》= left 或者 target 《= mid，則落在左區間。類似的可得出落在右區間的條件。

思路2： 先考慮target落在 left~mid的情況，然后再考慮落在 mid~right的情況。而每個區間又要考慮是不是有序的。