33 Search in Rotated Sorted Array

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)

29 Divide Two Integers

34 Search for a Range

Last modified 2yr ago

Copy link

Contents

33. Search in Rotated Sorted Array

1. Question

2. Implementation

3. Time & Space Complexity

33. Search in Rotated Sorted Array​

1. Question

2. Implementation

3. Time & Space Complexity

33. Search in Rotated Sorted Array