081.Search in Rotated Sorted Array II

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[1,3,1,1,1]
3
[1,1,3,1]
3
[1,1,1, 3,1]
3
[]
5
[1,1,1,1,1]
1
[1,1,1,2,2,2]
1
[1,1,1,2,2,2]
2

Solution 1: accepted 1ms

How to modularize the problem:
rotatedarray

Time: O(n) // worst case, when all elements are the same

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean search(int[] nums, int target) {
    if (nums.length == 0) return false;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target)
            return true;
        if (nums[mid] > nums[hi]) {
            if (target >= nums[lo] && target < nums[mid])
                hi = mid;
            else
                lo = mid;
        } else if (nums[mid] < nums[hi]) {
            if (target <= nums[hi] && target > nums[mid])
                lo = mid;
            else
                hi = mid;
        } else {
            hi--;
        }
    }
    if (nums[lo] == target || nums[hi] == target) 
        return true;
    return false;
}