153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
---
Suppose an array sorted in ascending order 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.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
Intuition
Sorted Array => Binary search with unknown target
Target is pivot .. or min element
Need to identify appropriate half to search
Make use of pivot relative to mid
while (lo <= hi)
if (lo == hi)
=> base case
=> terminate
=> return arr[lo]
if (arr[mid] < arr[hi])
=> strictly increasing upper half
=> discard upper half
=> mid is potential answer since its smaller
=> hi = mid
else
=> given no duplicates => arr[mid] > arr[hi]
=> pivot is somewhere between mid and hi
=> discard mid since it is higher .. cannot be ans
=> lo = mid + 1
---
Time - O(log N)
Space - O(1)
---
Related problems
---
