Find Minimum in Rotated Sorted Array

Why it belongs on this sheet

This problem is a nice example of binary search where the target is not a value but a structural turning point.

Pattern

Search for the pivot

Approach

Compare nums[mid] with nums[right]. If the midpoint is larger, the minimum must be to the right. Otherwise the minimum lies at mid or to its left.

Java solution

class Solution {
  public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
}

Complexity

• Time: O(log n)
• Space: O(1)

Interview note

Using right = mid instead of mid - 1 is important because mid itself can be the minimum.