Question

link

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.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">
              
              <a class="btn btn-xs btn-primary" href="/tag/array/">Array</a>
              
              <a class="btn btn-xs btn-primary" href="/tag/binary-search/">Binary Search</a>
  about/            
            </span>
          
        </div>

Solution

This question is simply a modified version of previous question. The special cases of the input makes it O(n) worst case complexity.

My Code

public class Solution {
    public int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    private int helper(int[] num, int left, int right) {
        if (num[left] < num[right] || left == right) {
            return num[left];
        } else if (num[left] == num[right]) {
            return helper(num, left + 1, right);
        } else if (left + 1 == right) {
            return num[right];
        }
        int mid = left + (right - left) / 2;
        if (num[mid] >= num[left]) {
            return helper(num, mid, right);
        } else {
            return helper(num, left, mid);
        }
    }
}