题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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.既然是二分搜索，每次就需要决定下次搜索的方向，我们可以将所有的搜索方向都列出来，方便我们分析合并。
1.二分后，左边的数组是升序的(nums[0]<nums[mid])
1.1 target>nums[mid]：应该往右边搜索
1.2 target<nums[mid]并且target<nums[0]：应该往右边搜索
1.3 target<nums[mid]并且target>=nums[0]：应该往左边搜索
2.二分后，左边的数组是存在翻转点的(nums[0]>nums[mid])
2.1 target<nums[mid]并且target>=nums[0]：应该往左边搜索
2.2 target<nums[mid]并且target<nums[0]：应该往左边搜索
2.3 target>nums[mid]并且target<nums[0]：应该往右边搜索
2.4 target>nums[mid]并且target>=nums[0]：应该往左边搜索
- 按照二分搜索模板，编写代码即可。
Java代码实现
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left+right)/2;
if(nums[mid] == target)
return mid;
else{
//左边这一半元素并非单纯的降序
if(nums[0]>nums[mid]){
//如果target比第一个元素大，说明target有可能在左边，因为右边的元素没有比nums[0]更大的了
if(target>=nums[0] || (target<=nums[0] && target<nums[mid]) ){
right = mid - 1;
}else{
left = mid + 1;
}
}
//左边这一半元素是单纯的升序
else{
//如果target>mid 或者 target<mid并且target<nums[0] target都可能在右边
if(target>nums[mid] || (target<nums[mid] && target<nums[0])){
left = mid + 1;
}else {
right = mid - 1;
}
}
}
}
return -1;
}
