假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進(jìn)行了旋轉(zhuǎn)。

（ 例如，數(shù)組 ［0，1，2，4，5，6，7］ 可能變?yōu)?［4，5，6，7，0，1，2］ ）。

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

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

你的算法時間復(fù)雜度必須是 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，就是有序數(shù)組，用二分來處理；否則，target可能落在 left~mid和mid~right兩個區(qū)間內(nèi)。

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

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