49. Search in Rotated Sorted Array && Search in Rotated Sorted Array II

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.

思路:找最小值,然后两边分别二分查找。

最小值找法:1. 只要小于上一个值即可。第一个只要小于最后一个(但是线性方法较慢) 2. 同样利用二分查找。

int binarySearch(int A[], int l, int h, int target) {
while(l <= h) {
int mid = (l+h) >> 1;
if(A[mid] > target) h = mid-1;
else if(A[mid] < target) l = mid+1;
else return mid;
}
return -1;
}
class Solution {
public:
int search(int A[], int n, int target) {
int low = 0, high = n-1, mid = 0;
while(A[low] > A[high]) {
if(low + 1 == high) {
mid = high;
break;
}
mid = (low + high) >> 1;
if(A[mid] < A[high]) high = mid;
else if(A[mid] > A[low]) low = mid;
}
return max(binarySearch(A, 0, mid-1, target), binarySearch(A, mid, n-1, target));
}
};

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

思路: 同上,除了找最小值时,需要在 A[l] = A[mid] = A[h] 这种情况时,顺序走一遍找中值。

int binarySearch(int A[], int l, int h, int target) {
while(l <= h) {
int mid = (l+h) >> 1;
if(A[mid] < target) l = mid+1;
else if(A[mid] > target) h = mid-1;
else return true;
}
return 0;
}
int getMid2(int A[], int l, int h, int target) {
int id = l;
while(++l < h) {
if(A[l] < A[l-1]) {
id = l;
}
}
return id;
}
int getMid(int A[], int n, int target) {
int l = 0, h = n-1, mid = 0;
while(A[l] >= A[h]) {
if(l + 1 == h) {
mid = h;
break;
}
mid = (l+h) >> 1;
if(A[mid] == A[h] && A[mid] == A[l]) return getMid2(A, l, h, target);
if(A[mid] <= A[h]) h = mid;
else if(A[mid] >= A[l]) l = mid;
}
return mid;
}
class Solution {
public:
bool search(int A[], int n, int target) {
int m = getMid(A, n, target);
return binarySearch(A, 0, m-1, target) || binarySearch(A, m, n-1, target); }
};
上一篇:基于Redis的CustomerSessionProvider(一)


下一篇:关于ArcGis的二次开发-基于ArcEngine10.2(内有安装包)