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