题目：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
题目要求是O(log n)时间复杂度，数组是有序数组经旋转得到两部分有序的数组（左部分最左值大于等于右部分最右值），可以用二分查找法来解决问题。由于是两部分有序，需要判断，target 和mid在哪个区域来维护二分查找的原则（查找区域有序）。
public class SearchRotatedSortedArray { public static int search(int[] nums, int target) { //处理特殊情况 //数组为null或者数组为空 if (nums == null || nums.length == 0) return -1; //处理业务逻辑 int l = 0; int r = nums.length - 1; while(l <=r){ int mid = l + (r - l >> 1); if (nums[mid] == target) return mid; //左部分有序区域 if (nums[l] <= nums[mid] ){ //目标在左部区域 if(nums[l]<=target && nums[mid]>target){ r = mid - 1; //目标在右部分区域 }else{ l = mid + 1; } } //右部分区域 if(nums[mid] <= nums[r]){ if (target > nums[mid] && target <= nums[r]) l = mid + 1; else r = mid - 1; } } return -1; } public static void main(String[] args) { int[] nums = {4,5,6,7,0,1,2}; System.out.println(search(nums,0)); } }
