Search in Rotated Sorted Array
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.
与Search in Rotated Sorted Array II,Find Minimum in Rotated Sorted Array,Find Minimum in Rotated Sorted Array II对照看
解法一：顺序查找 just a joke :D
class Solution {
public:
int search(int A[], int n, int target) {
for(int i = ; i < n; i ++)
{
if(A[i] == target)
return i;
}
return -;
}
};
解法二：二分查找
先用二分法找到最大元素，将数组切分成两个有序数组，再进行二分查找
class Solution {
public:
int search(int A[], int n, int target) {
if(n==)
return (target==A[])?:-;
//find the maximum first
int low = ;
int high = n-;
while(low < high)
{
int mid = (low+high)/;
if(A[mid] < A[low])
high = mid-;
else if(A[mid] > A[low])
low = mid;
else
{//low+1==high
if(A[high]>A[low])
low = high;
break;
}
}
int ind = low;
//to here, low is the index of maximum
//0~ind, ind+1~n-1 are two sorted arrays
if(target >= A[])
{//first array: 0~ind
low = ;
high = ind;
while(low <= high)
{
int mid = (low+high)/;
if(target == A[mid])
return mid;
else if(target > A[mid])
low = mid+;
else
high = mid-;
}
return -;
}
else
{//second array: ind+1, n-1
low = ind+;
high = n-;
while(low <= high)
{
int mid = (low+high)/;
if(target == A[mid])
return mid;
else if(target > A[mid])
low = mid+;
else
high = mid-;
}
return -;
}
}
};
解法三：可处理重复元素的二分查找，即不断去掉low与high元素
class Solution {
public:
int search(int A[], int n, int target) {
int low = ;
int high = n-;
while (low <= high)
{
int mid = (low+high)/;
if(A[mid] == target)
return mid;
if (A[low] < A[mid])
{
if(A[low] <= target && target < A[mid])
//binary search in sorted A[low~mid-1]
high = mid - ;
else
//subproblem from low to high
low = mid + ;
}
else if(A[mid] < A[high])
{
if(A[mid] < target && target <= A[high])
//binary search in sorted A[mid+1~high]
low = mid + ;
else
//subproblem from low to mid-1
high = mid - ;
}
else if(A[low] == A[mid])
low += ; //A[low]==A[mid] is not the target, so remove it
else if(A[mid] == A[high])
high -= ; //A[high]==A[mid] is not the target, so remove it
}
return -;
}
};
解法四：
二分查找，先对mid元素处于前半段还是后半段分情况讨论，再对target元素处于前半段还是后半段分情况讨论。
class Solution {
public:
int search(int A[], int n, int target) {
return search(A, , n-, target);
}
int search(int A[], int left, int right, int target)
{
if(left > right)
return -;
if(A[left] < A[right])
// one part, binary search
return binarySearch(A, left, right, target);
// else, two part
int mid = left + (right-left) / ; //prevent overflow
if(A[mid] == target)
return mid;
else if(A[left] > A[mid])
{// mid is in second part
if(target > A[mid])
{// target may be in the first part (case1), or second part after mid(case2)
if(target == A[left])
return left;
else if(target > A[left])
{// case1
return search(A, left, mid-, target);
}
else
{// case2
return search(A, mid+, right, target);
}
}
else
{// target is in the second part before mid
return search(A, left, mid-, target);
}
}
else
{// mid is in first part
if(target > A[mid])
{// target is in first part after mid
return search(A, mid+, right, target);
}
else
{// target may be in the first part before mid (case1), or second part
if(target == A[left])
return left;
else if(target > A[left])
{// case1
return search(A, left, mid-, target);
}
else
{// case2
return search(A, mid+, right, target);
}
}
}
}
int binarySearch(int A[], int left, int right, int target)
{
while(left <= right)
{
int mid = left + (right-left) / ; //prevent overflow
if(A[mid] == target)
return mid;
else if(A[mid] > target)
right = mid - ;
else
left = mid + ;
}
return -;
}
};