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;
}