153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.

• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums, return the minimum element of this array.

recursion

class Solution {
    public int findMin(int[] nums) {
        // if array is rotated, the first element will always larger than the last elememt
        // binary search
        return binarySearch(nums, 0, nums.length);
    }
    
    private int binarySearch(int[] nums, int start, int end){
        //end is the not searchaable
        int mid = (start+end)/2;
        if (mid==0 || mid==nums.length || nums[mid-1]>nums[mid]) return nums[mid%nums.length];
        if (nums[mid]>nums[0]) return binarySearch(nums, mid+1, end);
        else return binarySearch(nums, start, mid);   
    }
}

iterative

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        
// end not inculdded
        int end = nums.length;
        while (start<end){
            int mid = (start+end)/2;
            if (mid == 0 || nums[mid-1]>nums[mid]) return nums[mid];
            if (nums[mid]>nums[0]) start=mid+1;
            else end=mid;        
        }
        
        return nums[0];
    }
}

class Solution {
    public int findMin(int[] nums) {
        int start =0;
        // include the last element
        int end = nums.length-1;
        while(start<=end){
            int mid = (start+end)/2;
            if (mid>0 && nums[mid-1]>nums[mid]) return nums[mid];
            if (nums[mid]>=nums[0]) start=mid+1;
            else end = mid;
        }
        
        return nums[0];
    }
}