Search in Rotated Sorted Array 62
Question
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.
Challenge
O(logN) time
Solution
如果没有重复元素,就是二分搜索,mid要么落在大元素的区间,要么落在小元素的区间。先看mid落在前半区间还是后半区间,再看target是在该区间的前半部分还是后半部分。
代码如下:
No duplicate
public class Solution {
/**
*@param A : an integer rotated sorted array
*@param target : an integer to be searched
*return : an integer
*/
public int search(int[] A, int target) {
// write your code here
if (A == null || A.length == 0){
return -1;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end){
int mid = start + (end - start)/2;
if (A[mid] == target){
return mid;
}
if (A[start] < A[mid]){
if (A[start] <= target && target <= A[mid]){
end = mid;
}else{
start = mid;
}
}else{
if (A[mid] <= target && target <= A[end]){
start = mid;
}else{
end = mid;
}
}
}
if (A[start] == target){
return start;
}else if (A[end] == target){
return end;
}else{
return -1;
}
}
}
With duplicate
public class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target : an integer to be search
* return : a boolean
*/
public boolean search(int[] A, int target) {
// write your code here
if(A == null || A.length == 0){
return false;
}
for(int i = 0; i < A.length; i++){
if(A[i] == target){
return true;
}
}
return false;
}
}