Find Minimum in Rotated Sorted Array

Find the smallest value of a rotated sorted array by comparing the middle with the right end and keeping the half that holds the drop.

The idea

The minimum sits right after the drop. Compare nums[mid] with nums[hi]: if nums[mid] is bigger, the values fall somewhere between mid and hi, so the drop and the minimum are to the right of mid. Otherwise mid..hi rises steadily, so the minimum is mid itself or to its left. The window shrinks until lo == hi, and that index holds the minimum.

Code

public static 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];
}

Tips

• Compare with the right end, not the left: an array that is not rotated at all has nums[mid] < nums[hi] and correctly moves left.
• hi = mid, not mid - 1: mid may be the minimum, so it must stay in the window. That is also why the loop runs while lo < hi.
• The index of the minimum is the rotation count, which is the first step of the two-pass way to solve Search in Rotated Sorted Array.

In the .NET library

nums.Min() from LINQ gives the same answer in O(n); the point here is O(log n) by using the sorted structure.