LeetCode第33题：搜索旋转排序数组
这道题其实比较简单，排序好的数组，首先想到的就是二分查找，即便他挪过，那么二分最起码有一半是有序的，就可以判定出数据在不在这一半中间，则每一次递归都可以排除掉一半的数据，最终达到O(logN)的复杂度。
/**
* 解法：二分查找法，二分后一半有序，一半无序。有序那部分可以直接判断，不在范围内则舍弃那半部分
*/
public static int search2(int[] nums, int target) {
if (nums.length == 1) {
return nums[0] == target ? 0 : -1;
}
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
}
// 左右两组其中一组有序
if (nums[left] < nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid;
} else {
left = mid;
}
} else {
if (target > nums[mid] && target <= nums[right - 1]) {
left = mid;
} else {
right = mid;
}
}
}
return -1;
}
