Find Minimum in Rotated Sorted Array Optimal Binary Search Approach

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

Visualization Player

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❯

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

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class RotatedArrayMinimum {
  public static int findMin(int[] nums) {
    int start = 0;
    int end = nums.length - 1;

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

      if (nums[mid] > nums[end]) {
        // Minimum must be in the right half
        start = mid + 1;
      } else {
        // Minimum could be at mid or to the left
        end = mid;
      }
    }

    return nums[start]; // or nums[end], both are same here
  }

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

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	When the array is not rotated and the first element is the minimum.
Average Case	O(log n)	Each iteration of binary search reduces the array size by half, giving logarithmic performance.
Worst Case	O(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.

⬅ Previous TopicSearch in Rotated Sorted Array with Duplicates

Next Topic ⮕Find Rotation Count in Sorted Array

Comments

Loading comments...