Suppose a sorted array 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.
【题目分析】dan'sh
有一个没有重复元素的增序排序的数组,对这个数组进行玄旋转操作,然后在旋转后的数组中找到给定的target,如果找不到则返回-1。
【思路】
在一个有序的数组中查找一个数,最高效的就是二分查找。但是经过旋转操作以后数组分裂成了两段,在每一段中是有序的,这中情况下我们能对它使用二分查找嘛?
既然数组被分成了两段,如果我们使用二分查找能确定目标值在数组的哪段,然后改变查找的范围,那么就可以找到目标值。在二分查找的过程中要先确定中间位置的下标mid,通过中间值与最左边值的比较,我们可以确定中间值在数组中的哪一段,然后我们在比较目标值和中间值的大小,这样就能确定目标值的范围。举个例子如下:
- 目标值为6,nums[mid] = 7 > nums[left]。因此中间值在左边一段,此时nums[left]<target<=nums[mid],可以确定目标值在左边一段。right = mid;
- nums[mid] = 5 > nums[left]。因此中间值在左边一段,此时target>nums[mid]。left = mid + 1;
- nums[mid] = 6 = nums[left]。因此中间值在左边一段,此时target=nums[mid]。right = mid;
- left = right,找到目标值;
注意:
- 当中间值在数组的左段时,要确定目标值的位置不能这样判断:if(target <= nums[mid]),因为我们发现此时数组右段也是满足这个条件的,因此必须这样判断:if(target <= nums[mid] && target >= nums[left]),这样才能保证目标值位与中间值的左边,对于其他的情况目标值肯定在中间值的右边。
- 同理,当中间值在数组的右段时候,在确定目标值的位置时也要注意类似的情况。
- 这个算法对于一个没有旋转的增序排序数组也是适用的。
【java代码】
public class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= nums[l]) {
if (target <= nums[m] && target >= nums[l]) r = m;
else l = m + 1;
}else {
if (target > nums[m] && target <= nums[r]) l = m + 1;
else r = m;
}
}
return nums[l] == target ? l : -1;
}
}