Reference: Problem I & Problem II
Difficulty: Medium

My Post: Java Solution with Comments

Problem I

Suppose an array sorted in ascending order 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.

Your algorithm’s runtime complexity must be in the order of $O(\log{N})$.

Example:

1
2
3
4
5
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Analysis

Brute-Force

1
2
3
4
5
6
7
public int search(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] == target) return i;
}
return -1;
}

Time: $O(N)$
Space: $O(1)$

Use one binary search, but finding the pivot takes $O(N)$ time.

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
public int search(int[] nums, int target) {
int n = nums.length;
// Find the pivot
int idx = 0;
for (int i = 0; i < n - 1; ++i) { // O(N)
if (nums[i] > nums[i + 1]) {
idx = i + 1;
break;
}
}
// Binary search
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int realMid = (mid + idx) % n;
// no duplicate
if (nums[realMid] == target) return realMid;
if (nums[realMid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return -1;
}

Time: $O(N)$
Space: $O(1)$

Two Binary Searches

Use two binary searches. The first one is for finding the pivot.

The searching condition is nums[mid] <= nums[n - 1], which means we want to find the leftmost element that is less than the last element (the real first element).

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
27
28
29
30
// [4, 5, 6, 7, 0, 1, 2]
public int search(int[] nums, int target) {
int n = nums.length;

// search the index (the leftmost index that is less than the last element)
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= nums[n - 1]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
int idx = lo;

// search the target
lo = 0; hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int realMid = (mid + idx) % n;
if (nums[realMid] == target) return realMid;
if (nums[realMid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return -1;
}

Time: $O(\log{N})$
Space: $O(1)$

Problem II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example:

1
2
3
4
5
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

The original solution is not applicable when finding the pivot.

Example:

  • [1, 3, <1>, 1, 1]
  • [1, 1, 1, 3, <1>, 1, 1, 1, 1]

The index of the pivot will be $0$, which is not correct.

The solution is to do the processing as follows:

1
2
3
while (lo <= hi && nums[lo] == nums[hi]) {
lo += 1; // moving <lo> to a proper position
}

Note:

  • nums could be empty (length == 0) but not null.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public boolean search(int[] nums, int target) {

if (nums == null || nums.length == 0) {
return false;
}

int n = nums.length;
int lo = 0, hi = n - 1;

// pre-processing
while (lo <= hi && nums[lo] == nums[hi]) {
lo += 1; // moving lo to a proper place
}

// could be omitted. idx == lo == n ==> (mid + idx) % n == mid % n == mid
if (lo >= n) return nums[0] == target; // test cases: [1] or [1, 1]

// search the index
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= nums[n - 1]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
int idx = lo;

// search the target
lo = 0; hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int realMid = (mid + idx) % n;
if (nums[realMid] == target) return true;
if (nums[realMid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return false;
}

Time: $O(\log{N})$

  • $O(N)$ in the worst case (pre-processing).

Space: $O(1)$

Do it in one loop:

I don’t like this version. Not clear.

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

Comment