33 Search in Rotated Sorted Array

1. Question

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 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.

2. Implementation

(1) Binary Search
1
class Solution {
2
public int search(int[] nums, int target) {
3
if (nums == null || nums.length == 0) {
4
return -1;
5
}
6
7
int start = 0, end = nums.length - 1, mid = 0;
8
9
while (start + 1 < end) {
10
mid = start + (end - start) / 2;
11
12
if (nums[mid] == target) {
13
return mid;
14
}
15
else if (nums[mid] < nums[end]) {
16
if (nums[mid] < target && target <= nums[end]) {
17
start = mid + 1;
18
}
19
else {
20
end = mid - 1;
21
}
22
}
23
else {
24
if (nums[start] <= target && target < nums[mid]) {
25
end = mid - 1;
26
}
27
else {
28
start = mid + 1;
29
}
30
}
31
}
32
33
if (nums[start] == target) {
34
return start;
35
}
36
else if (nums[end] == target) {
37
return end;
38
}
39
else {
40
return -1;
41
}
42
}
43
}
Copied!

3. Time & Space Complexity

时间复杂度O(logn), 空间复杂度O(1)