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

在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標(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 開始 計數(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 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target ，則返回它的下標(biāo)，否則返回?-1?。

示例 1：輸入：nums = [4,5,6,7,0,1,2], target = 0

? ? ? ? ? ? ? 輸出：4

解題思路：設(shè)計一個時間復(fù)雜度為?O(log n)?的解決方案，即二分查找。

將數(shù)組一分為二，其中一定有一個是有序的，另一個可能是有序，也能是部分有序。此時有序部分用二分法查找。無序部分再一分為二，其中一個一定有序，另一個可能有序，可能無序。就這樣循環(huán)....

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

????????int?low?=?0;

????????int?high?=?nums.length?-?1;

????????while?(low?<=?high)?{

????????????int?mid?=?(low?+?high)/2;?// 定義中間值

????????????if(nums[mid]?==?target)?{?// 如果找到了直接返回

????????????????return?mid;

????????????}

????????????if(nums[mid]?<=?nums[high])?{ //如果右邊有序

????????????????if?(target?>=?nums[mid]?&&?target?<=?nums[high])?{??//target在有序部分，用二分法查找

????????????????????low?=?mid+1;

????????????????}?else?{???//target在無序部分，?再一分為二

????????????????????high?=?mid-1;

????????????????}

????????????}

????????????if(nums[mid]?>=?nums[low])?{?//如果左邊有序

????????????????if?(target?>=?nums[low]?&&?target?<=nums[mid])?{? //target在有序部分，用二分法查找

????????????????????high?=?mid-1;

????????????????}?else?{?//target在無序部分，再一分為二

????????????????????low?=?mid+1;

????????????????}

????????????}

????????}

????????return?-1; //未找到返回-1

????}