Find Minimum in Rotated Sorted Array

This one looks scary at first. A sorted array got rotated, and now you have to find the smallest number. The interviewer wants to see if you can still use binary search even when the array is not in perfect order. That is the real test here. Spot the pattern and the answer drops out fast.

🎯 The Problem

You get a sorted array that was rotated, and you must find the smallest number. Here are the rules.

• A rotation takes some numbers from the front and moves them to the back, keeping their order.
• So sorted [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].
• The result is two sorted pieces. The left piece and the right piece are each sorted.
• The smallest number sits right where the second piece begins.
• Find that smallest number. Every number is different.

In [4, 5, 6, 7, 0, 1, 2] the smallest number is 0, so the answer is 0.

Input:  nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Explanation: the array was the sorted [0,1,2,4,5,6,7] rotated, and 0 is the smallest value

Here is the rotated array. See how it climbs, then drops, then climbs again. The drop point holds the smallest number.

🐢 Approach 1: Linear Scan (Brute Force)

The idea in one line: look at every number and keep the smallest one you have seen.

The idea:

• Assume the first number is the smallest.
• Walk through the rest of the array.
• Each time you find a smaller number, remember it.

How it works:

• This is a plain linear scan. You visit every item, one after another.
• It always gives the right answer.

Why it is weak:

• The array is two sorted pieces, but the scan ignores that.
• For a big array you check every single number.
• That is O(n) time.

Here is the linear-scan code for that idea:

def find_min(nums):
    smallest = nums[0]
    for num in nums:
        smallest = min(smallest, num)
    return smallest

⚡ Approach 2: Binary Search on the Drop (Best)

The idea in one line: the smallest number sits at the single drop point, so binary search for that drop.

The idea:

• The array climbs, drops once, then climbs again.
• That single drop point is exactly where the smallest number lives.
• Keep two markers. lo is the left edge, hi is the right edge.

How it works:

• Pick the middle position mid. Compare the middle number with the number at hi, the rightmost in the window.
• If the middle is bigger than the number at hi, the drop is to the right. Move lo to mid + 1.
• If the middle is smaller than or equal to the number at hi, the right half is already sorted. The smallest is at mid or to its left. Move hi to mid.

Why it is fast:

• Move hi to mid, not mid - 1, because mid itself could be the smallest. Keep it in the window.
• Stop when lo and hi meet. They land on the smallest number.
• Each step halves the window, so this is O(log n) time.

Here is a dry run on [4, 5, 6, 7, 0, 1, 2]. Watch lo, mid and hi narrow toward the smallest value.

Steps to Solve

1. Set lo to 0 and hi to the last position of the array.
2. While lo is less than hi, keep narrowing the window.
3. Find the middle position mid as lo + (hi - lo) / 2.
4. If the number at mid is bigger than the number at hi, move lo to mid + 1.
5. Otherwise move hi to mid, keeping mid in the window.
6. When lo equals hi, the number at that position is the smallest. Return it.

#include <stdio.h>

int findMin(int nums[], int n) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;  // middle position
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;              // drop is to the right
        } else {
            hi = mid;                  // smallest is mid or left
        }
    }
    return nums[lo];                    // lo meets hi at the smallest
}

int main(void) {
    int nums[] = {4, 5, 6, 7, 0, 1, 2};
    printf("%d\n", findMin(nums, 7));
    return 0;
}

0

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;  // middle position
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;              // drop is to the right
        } else {
            hi = mid;                  // smallest is mid or left
        }
    }
    return nums[lo];                    // answer
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    cout << findMin(nums) << endl;
    return 0;
}

0

public class FindMin {
    public static int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;  // middle position
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;              // drop is to the right
            } else {
                hi = mid;                  // smallest is mid or left
            }
        }
        return nums[lo];                    // answer
    }

    public static void main(String[] args) {
        int[] nums = { 4, 5, 6, 7, 0, 1, 2 };
        System.out.println(findMin(nums));
    }
}

0

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2     # middle position
        if nums[mid] > nums[hi]:
            lo = mid + 1              # drop is to the right
        else:
            hi = mid                  # smallest is mid or left
    return nums[lo]                    # lo meets hi at the smallest


nums = [4, 5, 6, 7, 0, 1, 2]
print(find_min(nums))

0

function findMin(nums) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // middle position
    if (nums[mid] > nums[hi]) {
      lo = mid + 1; // drop is to the right
    } else {
      hi = mid;     // smallest is mid or left
    }
  }
  return nums[lo];  // answer
}

const nums = [4, 5, 6, 7, 0, 1, 2];
console.log(findMin(nums));

0

Let us walk through the Python version line by line, so the logic feels clear.

The line lo, hi = 0, len(nums) - 1 sets the two edges. lo is the first position and hi is the last. The smallest number is somewhere inside this window.

The line while lo < hi: keeps shrinking the window. Notice it is <, not <=. We stop the moment the two edges meet on one number, and that number is the answer.

The line mid = lo + (hi - lo) // 2 picks the middle position. We write it this way to stay safe from overflow in other languages, and it gives the same middle.

The line if nums[mid] > nums[hi]: is the heart of the trick. We compare the middle number with the rightmost number in our window. If the middle is bigger, the window is “broken” on the right side. The drop must be after mid. So we set lo = mid + 1 and throw the left half away.

The else branch covers the case where the middle is smaller than or equal to the rightmost number. That means the right part is neat and sorted. The smallest value is at mid or to its left. So we set hi = mid. We keep mid itself, because mid might be the smallest.

When the loop ends, lo and hi point at the same spot. The line return nums[lo] hands back the smallest number.

⏱️ Time and Space Complexity

The linear scan looks at every number, so it is O(n). The binary search halves the window each step, so it finishes in about log n steps. Both use only a few variables, so the space is O(1).

🧩 Key Takeaways

• ✅ A rotated sorted array is two sorted pieces with one drop between them.
• ✅ The smallest number sits exactly at that drop point.
• ✅ Compare the middle value with the value at hi to decide which half to keep.
• ✅ Move hi to mid, not mid - 1, so you never skip the smallest value.
• ✅ The window halves each step, giving O(log n) time.

🚀 What’s Next?

• Binary Search
• Search a 2D Matrix