153. Find Minimum in Rotated Sorted Array

#binary-search

Problem

Find Minimum in Rotated Sorted Array - LeetCodeLeetCode

Intuition

Array is sorted in non decreasing order

At every iteration, we need to eliminate half the entries. That's the basic of binary search.

Here we do not have any specified target to search for, we need to find minimum values in ROTATED SORTED ARRAY.

We will perform normal binary search, and at every iteration we will check if the sub array we have gotten from low to mid is left sorted or right sorted.

• If the sub array is left sorted, minimum will always be on low

• If the sub array is right sorted, minimum will always be on mid

Time Complexity

O(log n)

Space Complexity

O(n)

Solution

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length -1;

        int min = Integer.MAX_VALUE;

        while(low <= high) {
            int mid = low + (high - low)/2;

            if(nums[low] <= nums[mid]) { // Left sorted
                // If left sorted, min number in left subarray will be on low
                min = Math.min(min, nums[low]); 
                low = mid + 1;
            } else { // Right sorted
                // If right sorted, min number in right subarray will be on mid
                min = Math.min(min, nums[mid]);
                high = mid - 1;
            }
        }
        return min;
    }
}