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.
用二分查找去做
public int search(int[] A, int target) {
int first = 0, last = A.length;
while (first != last) {
int mid = (first + last) / 2;
if (A[mid] == target)
return mid;
if (A[first] <= A[mid]) {
if (A[first] <= target && target < A[mid])
last = mid;
else
first = mid + 1;
} else {
if (A[mid] < target && target <= A[last - 1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
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[m]>=A[l], 那么[l,m] 为递增序列的假设就不能成立了，比如[1,3,1,1,1]。
如果A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件：
• 若A[m]>A[l]，则区间[l,m] 一定递增
• 若A[m]==A[l] 确定不了，那就l++，往下看一步即可。
因此复杂度从O(lgn)变成了O(n)。具体说明参见剑指offer上查找旋转数组的最小元素。
public boolean search(int[] A, int target) {
int first = 0, last = A.length;
while (first != last) {
int mid = (first + last) / 2;
if (A[mid] == target)
return true;
if (A[first] < A[mid]) {
if (A[first] <= target && target < A[mid])
last = mid;
else
first = mid + 1;
} else if (A[first] > A[mid]) {
if (A[mid] < target && target <= A[last - 1])
first = mid + 1;
else
last = mid;
} else {
first++;
}
}
return false;
}