题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
思路：
做有序数组的二分查找时，定义两个指针l和r，
- 初始状态，
l = 0，r = nums.length - 1，在l <= r的条件下做循环，每次折掉一半数据； - 每次循环算出
l和r范围内中间的位置mid = l + ((r - l) >> 1)，
1.如果目标值target == nums[mid]，直接返回；
2.如果target > nums[mid]那target肯定在mid的右边(更新l,l = mid + 1)，否则在左边(更新r,r = mid - 1)。
而我们这题的数组有可能发生了旋转，那么就不能单纯依据target和nums[mid]的比较来判断target在mid的左还是在右。
- 左右部分有无序，分为三种情况:
1.左无序，右肯定有序 2.右无序，左肯定有序 3.左右都有序，而判断无序的条件是最左边元素 > 最右边元素 - 如果左边有序，那么就通过判断
target是否落在左边来判断target在左还是在右；如果右边有序，那么就通过判断target是否落在右边来判断target在左还是在右；反正，谁有序就用谁来判断，因为判断条件是最左边元素 < target < 最右边元素。
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int l = 0, 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(target >= nums[mid] && target <= nums[r]){
l = mid + 1;
}else{
r = mid - 1;
}
//右部分无序，左部分有序
}else if(nums[mid] > nums[r]){
if(target <= nums[mid] && target >= nums[l]){
r = mid - 1;
}else{
l = mid + 1;
}
//左右部分都有序
}else{
if(target <= nums[mid] && target >= nums[l]){
r = mid - 1;
}else{
l = mid + 1;
}
}
}
return -1;
}
}
这里的mid也纳入了左或右部分，而不是左：l->mid-1，右：mid+1->r。这是为了减少边界的处理。
以下代码：左：l->mid-1，右：mid+1->r
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int l = 0, r = nums.length - 1;
while(l <= r){
int mid = l + ((r - l) >> 1);
if(nums[mid] == target){
return mid;
}
//左部分无序，右部分有序
if(mid - 1 >= l && nums[l] > nums[mid - 1]){
if(mid + 1 <= r && target >= nums[mid + 1] && target <= nums[r]){
l = mid + 1;
}else{
r = mid - 1;
}
//右部分无序，左部分有序
}else if(mid + 1 <= r && nums[mid + 1] > nums[r]){
if(mid - 1 >= l && target <= nums[mid - 1] && target >= nums[l]){
r = mid - 1;
}else{
l = mid + 1;
}
//左右部分都有序
}else{
if(mid - 1 >= l && target <= nums[mid - 1] && target >= nums[l]){
r = mid - 1;
}else{
l = mid + 1;
}
}
}
return -1;
}
}
由于判断条件使用到mid - 1和mid + 1的操作，可能会导致数组越界。
