Search in a Rotated Array问题
1.问题描述
Suppose an array sorted in ascending order 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.
题目翻译:
一个按照递增排序的数组,在某个未知的位置发生反转,例如[0,1,2,4,5,6,7]可能变成[4,5,6,7,0,1,2],在这个数组中找到一个数值并返回索引,如果不存在返回-1。
数组中没有重复的数字存在。
2.解题思路
读完题目这是一道在已排序的数组中寻找一个数值,这类问题的基本解决思路就是利用二分查找。这道题设置的难点就是在某个位置把顺序翻转,就不能按照原始的二分查找的方法来算。
发生顺序的反转肯定是把大的数字翻转到前面,那么按照就存在反转的数目是否越中间位置,以及target和中间位置数值的大小关系,可以把问题分为四种情况:
- 大数值反转越过中间位置,查找小数字
- 大数值反转越过中间位置,查找大数字
- 大数值没有越过中间位置,查找小数字
- 大数值没有越过中间位置,查找大数字
这是想这道题最基本的解决思路,是不是可以优化呢?
当然可以,无论在那个位置翻转,总有一半的数据在保持一定的递增顺序,只要找到target所在的那一半的数据,就能利用二分很快的找到target的索引。
还可以找到发生反转的位置,然后利用二分查找target的位置,这个思路很巧妙,它利用发生翻转的位置来寻找没有翻转时候的中心位置,很值得借鉴。
3.代码实现
第一种方法的实现:
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if(nums==null||len==0)
return -1;
int low = 0,high = len-1;
int mid = 0;
System.out.println("flag2");
while(low<high){
mid = low+(high-low)/2;
if(target==nums[mid])
return mid;
if(nums[low]<=nums[mid]){
if(target>=nums[low]&&target<=nums[mid])
high=mid-1;
else{
low = mid+1;
}
}
else if(nums[low] >=nums[mid]){
if(target>=nums[low]&&target>=nums[mid]||target<=nums[low]&&target<=nums[mid])
high = mid-1;
else
low = mid+1;
}
}
return target==nums[low]?low:-1;
}
}
第二种方法的实现:
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if(nums==null||len==0)
return -1;
int low = 0,high = len-1;
int mid = 0;
while(low<high){
mid = low+(high-low)/2;
if(target==nums[mid])
return mid;
if(nums[low]<=nums[mid]){
if(target>=nums[low]&&target<nums[mid])
high=mid-1;
else
low = mid+1;
}
else{
if(target>=nums[low]||target<nums[mid])
high = mid-1;
else
low = mid+1;
}
}
return target==nums[low]?low:-1;
}
}
第三种方法的实现:
class Solution {
public:
int search(int A[], int n, int target) {
int lo=0,hi=n-1;
// find the index of the smallest value using binary search.
// Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
// Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
while(lo<hi){
int mid=(lo+hi)/2;
if(A[mid]>A[hi]) lo=mid+1;
else hi=mid;
}
// lo==hi is the index of the smallest value and also the number of places rotated.
int rot=lo;
lo=0;hi=n-1;
// The usual binary search and accounting for rotation.
while(lo<=hi){
int mid=(lo+hi)/2;
int realmid=(mid+rot)%n;
if(A[realmid]==target)return realmid;
if(A[realmid]<target)lo=mid+1;
else hi=mid-1;
}
return -1;
}
};