题目描述：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 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）如果在中点直接找到了目标值，就直接返回；（2）否则比较左端点值和中值，若左端点值小于等于中值，说明左半部分有序，如果target刚好落在左半部分，则在左半部分查找，否则到右半部分查找；（3）若不满足左端点值小于等于中值，说明右半部分有序，如果target刚好落在右半部分，则在右半部分查找，否则到左半部分查找；（4）退出循环时，没有找到target，说明不存在，返回 -1。
代码实现
class Solution { //采用二分搜索 //如果nums[left] < nums[mid]，说明前一半有序，如果nums[left] < target < nums[mid]，则在前一半中找，否则在后一半中找 //如果nums[left] > nums[mid]，说明后一半有序，如果nums[mid] < target < nums[right]，则在后一半中找，否则在前一半中找 public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){//注意，这里是小于等于，而不是小于，因为当左右指针重叠的时候也算在内 int mid = (left + right) / 2; //找到了直接返回 if(target == nums[mid]){ return mid; } //然后再在有序的那一部分找 //前面一半有序 if(nums[left] <= nums[mid]){ //这里必须是小于等于，因为当left和mid指向同一个数的时候，也表示有序情况 if(nums[left] <= target && target <= nums[mid]){ //等于表示在范围内，可能落在两个端点上 right = mid - 1; } else left = mid + 1; } //后一半有序 else{ if(nums[mid] <= target && target <= nums[right]){ //等于表示在范围内，可能落在两个端点上 left = mid + 1; } else right = mid - 1; } } //没有找到，返回-1 return -1; } }