Binary Search - Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array, find the minimum element. All elements are unique.

Input: [3,4,5,1,2] → Output: 1

Input: [4,5,6,7,0,1,2] → Output: 0

Binary search: if nums[mid] > nums[hi], the minimum is in the right half. Otherwise it is in the left half (including mid).

While lo < hi:
mid = lo + (hi-lo)/2.
If nums[mid] > nums[hi]: minimum must be in right half, lo = mid+1.
Else: minimum is in left half (possibly mid), hi = mid.
Return nums[lo].

class Solution { public int findMin(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid; } return nums[lo]; } }

Time Complexity: O(log N)
Space Complexity: O(1)