Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array 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).

Find the minimum element.

The array may contain duplicates.

Solution:

  1. public class Solution {
  2.   public int findMin(int[] a) {
  3.     return search(a, 0, a.length - 1);
  4.   }
  6.   int search(int[] a, int lo, int hi) {
  7.     // a[] is sorted
  8.     if (lo > hi) {
  9.       return a[0];
  10.     }
  12.     int mid = lo + (hi - lo) / 2;
  14.     if (mid > 0 && a[mid - 1] > a[mid]) {
  15.       return a[mid];
  16.     }
  18.     if (mid < a.length - 1 && a[mid] > a[mid + 1]) {
  19.       return a[mid + 1];
  20.     }
  22.     if (a[lo] == a[mid] && a[mid] == a[hi]) {
  23.       return Math.min(search(a, lo, mid - 1), search(a, mid + 1, hi));
  24.     }
  26.     if (a[lo] <= a[mid]) {
  27.       return search(a, mid + 1, hi);
  28.     } else {
  29.       return search(a, lo, mid - 1);
  30.     }
  31.   }
  32. }