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.
Example
For [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1.
分析:
判断Mid处于上半段还是下半段后,在单调递增/递减区间内可以判断,否则丢回去继续while
解法:
public int search(int[] A, int target) {
// write your code here
if(A.length == 0)
return -1;
int s = 0, e = A.length - 1;
while(s + 1 < e){
int m = s + (e - s)/2;
if (A[m] == target) {
return m;
}
if(A[m] > A[s]){//m在上半段
if(A[s] <= target && target <= A[m]){//在单调递增区间才能判定,否则还是2条断线,丢回去继续while
e = m;
}else{
s = m;
}
}
else{
if(A[m] <= target && target <= A[e]){
s = m;
}else{
e = m;
}
}
}
if(A[s] == target)
return s;
if(A[e] == target)
return e;
return -1;
}
Last updated
Was this helpful?