整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。

在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個(gè)下標(biāo) k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計(jì)數(shù)）。例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。

給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個(gè)整數(shù) target ，如果 nums 中存在這個(gè)目標(biāo)值 target ，則返回它的下標(biāo)，否則返回 -1 。

你必須設(shè)計(jì)一個(gè)時(shí)間復(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

示例 3：

輸入：nums = [1], target = 0

輸出：-1

因?yàn)橐猯gn的復(fù)雜度，所以想到二分法；

由提供的旋轉(zhuǎn)的條件可以發(fā)現(xiàn)，如果從中間砍一刀變成兩個(gè)序列的話，必有一個(gè)是有序的；

判斷一個(gè)值是否在無(wú)序區(qū)間需要遍歷，而判斷一個(gè)值是否在有序區(qū)間卻只需要將target與兩端進(jìn)行比較即可；

而逆轉(zhuǎn)數(shù)組的無(wú)序段和有序段的一個(gè)顯著標(biāo)志就是段頭是否小于段尾；

因此本題的算法應(yīng)該是將數(shù)組不斷二分，在每一次二分的過程中，先找到有序區(qū)間， 然后若通過對(duì)比發(fā)現(xiàn)target在有序區(qū)間，那另一端可以直接舍棄；否則就完全可以將有序區(qū)間舍棄。

這樣就可以加速二分法；

代碼如下：