Find Minimum in Rotated Sorted Array

ArrayBinary Search
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

# Solution

nums[-1] and nums[mid] is either the min, or >= min.

let res be the index of the minimum element

binary search in 0..n-2

if nums[mid] < nums[-1], two cases:

  1. nums[mid] is in monotonically increasing array
  2. nums[mid] is in the second part of rotated array

in both cases, nums[mid] is min or > min

it's impossible that nums[mid] == nums[-1]

if nums[mid] > nums[-1], the 1st case is impossible: nums[mid] is in monotonically increasing array nums[mid] is in the first part of rotated array, and mid < res

if nums[mid] < nums[mid - 1], return nums[mid] else, search left half

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        lo, hi = 0, n-2
        while lo <= hi:
            mid = (lo+hi) // 2
            if nums[mid] < nums[-1]:
                hi = mid - 1
            else:
                lo = mid + 1
        return nums[lo]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        lo, hi = 0, n-1
        while lo < hi:
            mid = (lo+hi) // 2
            if nums[mid] < nums[hi]:
                hi = mid
            else:
                lo = mid + 1
        return nums[lo]
1
2
3
4
5
6
7
8
9
10
11

Find Peak Element