?

?題解：

/*** 旋轉排序數組可分為N1 + N2兩個部分，如：[4,5,6,7,1,2,3]，N1為[4,5,6,7]，N2為[1,2,3]** 必然滿足以下兩個條件：* 1. N1和N2都是分別遞增的；* 2. N1中的所有元素大于N2中的所有元素;** 以上兩個條件可推出：nums[0]是N1中最小的數，即nums[0] > N2中的所有元素** 而mid不是在N1內就是在N2內，如果在N1內，則在N1內使用二分查找，否則在N2內使用二分查找* 所以：如果nums[0] <= nums[mid]，即mid落在了N1內，則[0, mid]肯定是有序的*       否則mid落在了N2內，則[mid, n)肯定是有序的**/
if (nums[0] <= nums[mid]) {// 左半邊有序
} else {// 右半邊有序
}

先判斷nums[mid]是在旋轉數組的左半邊，還是右半邊；

如果在左半邊然后使用target和nums[0]和nums[mid]作比較，target處于[0,mid]中間，right = mid - 1; else left = mid + 1;

如果在右半邊，使用target和nums[mid] nums[nums.length-1]作比較，target處于[mid,nums[nums.length-1]], left = mid + 1,否則right = mid-1

代碼

public int search(int[] nums, int target) {if(nums.length == 0){return -1;    }int left = 0, right = nums.length - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target){return mid;}//左半邊有序，在左半邊使用二分查找if(nums[mid] >= nums[0]){if(nums[0] <= target && target < nums[mid]){ //target處于[0,mid)，向左移動mid            right = mid - 1;}else{left = mid + 1;}}//右半邊有序，在右半邊使用二分查找else{if(nums[mid] < target && target <= nums[nums.length - 1]){left = mid + 1;}else{right = mid - 1;}}}return -1;}