Leetcode: Find Minimum In Rotated Sorted Array

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.

You may assume no duplicate exists in the array.

Runtime Analysis:

Runtime: O(log n)

It is quite easy to scan the array, checking for the first point that the sequence is no longer increasing. This approach takes O(n) runtime, but that isn't what this question is testing for. You can actually use a modified Binary Search Algorithm to find the pivot for this question.

Algorithmic Approach:

In Binary Search, it is always important to sort out the main cases separately.

1. Arr[i] > Arr[i-1] && Arr[i] > Arr[i+1]: We found our peak element!
2. Arr[left] > Arr[i] && Arr[right] > Arr[i]: Peak is in the left half!                           3. Arr[left] < Arr[i] && Arr[right] < Arr[i]: Peak is in the right half!

Given these 3 basic cases, there are some other cases to consider:
1. What if the Array is completely ascending?
2. What if the Array is completely descending?

Java Code: 

public class Solution {
    public int findMin(int[] num) {
        int val = helper(num, 0, num.length-1);
        return val;
    }
    
    public int helper(int [] num, int left, int right){
        if(left > right)
            return -1;
        
        // only 1 element left
        if(left == right)
            return num[left];
        
        // only 2 elements left
        if(right - left == 1){
            return Math.min(num[left], num[right]);
        }
        
        int mid = (left + right) / 2;
        
        // we find the smallest element when the value to left and value to right are both greater
        // we need to cover edge cases as well, if mid is on the far left or far right
        
        if(num[mid] < num[mid-1] && num[mid] < num[mid+1]){
            return num[mid];
        }
        
        // right half is sorted 
        else if(num[left] > num[mid] && num[right] > num[mid]){
            return helper(num, left, mid-1);    
        }
        // left half is sorted 
        else if(num[left] < num[mid] && num[right] < num[mid]){
            return helper(num, mid+1, right);
        }
        // completely ascending sorted 
        else if(num[left] < num[mid] && num[right] > num[mid]){
            return helper(num, left, mid-1);
        }
        // completely inverse sorted
        else{
            return -1;
        }
        


    }
    
}
 public class Solution {
    public int findMin(int[] num) {
        int val = helper(num, 0, num.length-1);
        return val;
    }
    
    public int helper(int [] num, int left, int right){
        if(left > right)
            return -1;
        
        // only 1 element left
        if(left == right)
            return num[left];
        
        // only 2 elements left
        if(right - left == 1){
            return Math.min(num[left], num[right]);
        }
        
        int mid = (left + right) / 2;
        
        
        if(num[mid] < num[mid-1] && num[mid] < num[mid+1]){
            return num[mid];
        }
        
        // right half is sorted 
        else if(num[left] > num[mid] && num[right] > num[mid]){
            return helper(num, left, mid-1);    
        }
        // left half is sorted 
        else if(num[left] < num[mid] && num[right] < num[mid]){
            return helper(num, mid+1, right);
        }
        // completely ascending sorted 
        else if(num[left] < num[mid] && num[right] > num[mid]){
            return helper(num, left, mid-1);
        }
        // completely inverse sorted
        else{
            return -1;
        }
        

    }
    
}