Find Minimum in Rotated Sorted Array Optimal Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a rotated sorted array of unique integers, your task is to find the minimum element in the array.

A rotated sorted array is an array that was originally sorted in increasing order, but then some leading elements were moved to the end. For example, [1, 2, 3, 4, 5] could become [3, 4, 5, 1, 2].

The array contains no duplicate elements. If the array is empty, return -1.

Examples❯

Input Array Output Description
[4, 5, 6, 7, 0, 1, 2] 0 Array is rotated, minimum is at the pivot (index 4)
[3, 4, 5, 1, 2] 1 Minimum element is in the middle of the array
[1, 2, 3, 4, 5] 1 Array is not rotated, minimum is at index 0
[2, 1] 1 Two elements, rotated once
[1] 1 Single element array
[] -1 Empty array, no elements to check

Solution❯

Understanding the Problem

We are given a rotated sorted array — an array that was originally sorted in increasing order but has been rotated at some pivot point. Our task is to find the minimum element in this array efficiently.

For example, a sorted array [1, 2, 3, 4, 5] might become [4, 5, 1, 2, 3] after rotation. The goal is to identify the smallest number — in this case, 1 — without checking each element one by one.

Step-by-Step Solution with Example

Step 1: Observe if the array is already sorted

If the array is not rotated at all, the first element will be less than the last. In that case, the first element is the smallest. For example, [1, 2, 3, 4, 5] — here, 1 < 5, so the minimum is 1.

Step 2: Initialize Binary Search

We'll use binary search because the array has a sorted structure. Initialize two pointers: low = 0 and high = array.length - 1.

Step 3: Loop until the search space is narrowed

While low < high, do the following:

  • Calculate mid = Math.floor((low + high) / 2).
  • If array[mid] > array[high], it means the minimum is to the right of mid. So, set low = mid + 1.
  • Otherwise, the minimum is at mid or to the left. Set high = mid.

Step 4: Return the minimum element

After the loop ends, low == high, and we have found the index of the minimum element. Return array[low].

Step 5: Example Walkthrough

Let’s take [4, 5, 6, 1, 2, 3] as an example:

  • Initial: low = 0, high = 5
  • mid = 2 → array[2] = 6, array[5] = 3 → 6 > 3 → minimum must be on the right → low = 3
  • mid = 4 → array[4] = 2, array[5] = 3 → 2 ≤ 3 → high = 4
  • mid = 3 → array[3] = 1, array[4] = 2 → 1 ≤ 2 → high = 3
  • Now low = high = 3 → minimum = array[3] = 1

Edge Cases

  • Array not rotated: [1, 2, 3, 4, 5] → min = 1
  • Single element: [7] → min = 7
  • Two elements: [10, 5] → min = 5
  • Empty array: Return -1 or handle as an invalid input

Finally

This approach is optimal because it uses binary search, which has a time complexity of O(log n). By recognizing whether to move left or right based on the middle and end values, we efficiently narrow the search space. This method is both intuitive and scalable for large datasets.

Algorithm Steps❯

  1. Initialize two pointers: start = 0 and end = n - 1.
  2. While start < end:
  3. → Compute mid = start + (end - start) / 2.
  4. → If arr[mid] > arr[end], it means the minimum is in the right half, so set start = mid + 1.
  5. → Else, the minimum is in the left half including mid, so set end = mid.
  6. When the loop ends, arr[start] is the minimum element.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findMin(int* nums, int numsSize) {
    int start = 0, end = numsSize - 1;

    while (start < end) {
        int mid = start + (end - start) / 2;

        if (nums[mid] > nums[end]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return nums[start];
}

int main() {
    int nums[] = {4, 5, 6, 7, 0, 1, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Minimum Element: %d\n", findMin(nums, size));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)When the array is not rotated and the first element is the minimum.
Average CaseO(log n)Each iteration of binary search reduces the array size by half, giving logarithmic performance.
Worst CaseO(log n)In the worst case, the binary search continues until only one element remains.

Space Complexity❯

O(1)

Explanation: Only a few pointers are used, and no extra space is required.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...