Minimum in Rotated Sorted Array

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.

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.

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.

#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;
}

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

int findMin(vector<int>& nums) {
    int start = 0, end = nums.size() - 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() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    cout << "Minimum Element: " << findMin(nums) << endl;
    return 0;
}

def find_min(nums):
    start, end = 0, len(nums) - 1

    while start < end:
        mid = start + (end - start) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid

    return nums[start]

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

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]) {
        start = mid + 1;
      } else {
        end = mid;
      }
    }
    return nums[start];
  }

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

function findMin(nums) {
  let start = 0;
  let end = nums.length - 1;

  while (start < end) {
    let mid = Math.floor(start + (end - start) / 2);

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

  return nums[start];
}

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

package main

import (
    "fmt"
)

func findMin(nums []int) int {
    start, end := 0, len(nums)-1

    for start < end {
        mid := start + (end-start)/2
        if nums[mid] > nums[end] {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return nums[start]
}

func main() {
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    fmt.Println("Minimum Element:", findMin(nums))
}

fn find_min(nums: &[i32]) -> i32 {
    let (mut start, mut end) = (0, nums.len() - 1);
    while start < end {
        let mid = start + (end - start) / 2;
        if nums[mid] > nums[end] {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    nums[start]
}

fn main() {
    let nums = vec![4, 5, 6, 7, 0, 1, 2];
    println!("Minimum Element: {}", find_min(&nums));
}

fun findMin(nums: IntArray): Int {
    var start = 0
    var end = nums.size - 1

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

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

fun main() {
    val nums = intArrayOf(4, 5, 6, 7, 0, 1, 2)
    println("Minimum Element: ${findMin(nums)}")
}

func findMin(_ nums: [Int]) -> Int {
    var start = 0
    var end = nums.count - 1

    while start < end {
        let mid = start + (end - start) / 2
        if nums[mid] > nums[end] {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return nums[start]
}

let nums = [4, 5, 6, 7, 0, 1, 2]
print("Minimum Element: \(findMin(nums))")

function findMin(nums: number[]): number {
  let start = 0;
  let end = nums.length - 1;

  while (start < end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (nums[mid] > nums[end]) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  return nums[start];
}

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

Time complexity

Space complexity

O(1)

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