A sorted array of distinct numbers was rotated at some unknown point. Find its minimum in O of log n time.
DSA Animator › DSA Revision › Binary Search › Find Minimum in Rotated Sorted Array
Remember: compare mid with the right end to see which side holds the drop. The minimum is the start of the second sorted run. The video solves Find Minimum in Rotated Sorted Array (LeetCode 153, Medium) with the Binary Search pattern from the Binary Search topic, and you can replay every step in the interactive Find Minimum in Rotated Sorted Array animation.
A sorted array of distinct numbers was rotated at some unknown point. Find its minimum in O of log n time.
For 4, 5, 6, 7, 0, 1, 2, the minimum is 0.
Scanning every element is O of n. The rotation leaves two sorted runs, and the minimum is where the second run starts.
Compare the middle with the last element of the range. If the middle is bigger, the drop happens to the right, so the minimum is on the right. Otherwise, the minimum is at mid or to its left.
Low 0, high 6, mid 3 holds 7, bigger than 2, so low becomes 4. Mid 5 holds 1, smaller than 2, so high becomes 5. Mid 4 holds 0, smaller than 1, so high becomes 4. Low equals high at index 4, and the minimum is 0.
In code, loop while low is less than high. If the middle value is bigger than the value at high, move low to mid plus 1. Otherwise move high to mid, and return the value at low, so it's O of log n time.
Remember: compare mid with the right end to see which side holds the drop. The minimum is the start of the second sorted run.