Find Minimum in Rotated Sorted Array

Prereq: Vanilla Binary Search and Finding the Boundary with Binary Search

A sorted array of unique integers was rotated at an unknown pivot. For example, [10, 20, 30, 40, 50] becomes [30, 40, 50, 10, 20]. Find the index of the minimum element in this array. All the numbers are unique.

Input: [30, 40, 50, 10, 20]

Output: 3

Explanation: the smallest element is 10 and its index is 3.

Input: [3, 5, 7, 11, 13, 17, 19, 2]

Output: 7

Explanation: the smallest element is 2 and its index is 7.

Try it yourself

Explanation

At first glance, it seems that there's no way to do it in less than linear time. The array is not sorted.

But remember binary search can work beyond sorted arrays, as long as there is a binary decision we can use to shrink the search range.

Let's draw a figure and see if there's any pattern. If we plot the numbers against their index, we get:

Notice the numbers are divided into two sections: numbers larger than the last element of the array and numbers smaller than it. The minimum element is at the boundary between the two sections.

We can apply a filter of < the last element and get the boolean array that characterizes the two sections.

Now the problem is yet again reduced to finding the first true element in a boolean array. And we already know how to do this from Find the Boundary module.

Time Complexity: O(log(n))

1from typing import List
2
3def find_min_rotated(arr: List[int]) -> int:
4    left, right = 0, len(arr) - 1
5    boundary_index = -1
6
7    while left <= right:
8        mid = (left + right) // 2
9        # if <= last element, then belongs to lower half
10        if arr[mid] <= arr[-1]:
11            boundary_index = mid
12            right = mid - 1
13        else:
14            left = mid + 1
15
16    return boundary_index
17
18if __name__ == '__main__':
19    arr = [int(x) for x in input().split()]
20    res = find_min_rotated(arr)
21    print(res)
22

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int findMinRotated(List<Integer> arr) {
8        int left = 0;
9        int right = arr.size() - 1;
10        int boundaryIndex = -1;
11        while (left <= right) {
12            int mid = left + (right - left) / 2;
13            // if <= last element, then belongs to lower half
14            if (arr.get(mid) <= arr.get(arr.size() - 1)) {
15                boundaryIndex = mid;
16                right = mid - 1;
17            } else {
18                left = mid + 1;
19            }
20        }
21        return boundaryIndex;
22    }
23
24    public static List<String> splitWords(String s) {
25        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
26    }
27
28    public static void main(String[] args) {
29        Scanner scanner = new Scanner(System.in);
30        List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
31        scanner.close();
32        int res = findMinRotated(arr);
33        System.out.println(res);
34    }
35}
36

1function findMinRotated(arr) {
2    let left = 0;
3    let right = arr.length - 1;
4    let boundary_index = -1;
5    while (left <= right) {
6        let mid = left + Math.floor((right - left) / 2);
7        // if <= last element, then belongs to lower half
8        if (arr[mid] <= arr[arr.length - 1]) {
9            boundary_index = mid;
10            right = mid - 1;
11        } else {
12            left = mid + 1;
13        }
14    }
15    return boundary_index;
16}
17
18function splitWords(s) {
19    return s == "" ? [] : s.split(' ');
20}
21
22function* main() {
23    const arr = splitWords(yield).map((v) => parseInt(v));
24    const res = findMinRotated(arr);
25    console.log(res);
26}
27
28class EOFError extends Error {}
29{
30    const gen = main();
31    const next = (line) => gen.next(line).done && process.exit();
32    let buf = '';
33    next();
34    process.stdin.setEncoding('utf8');
35    process.stdin.on('data', (data) => {
36        const lines = (buf + data).split('\n');
37        buf = lines.pop();
38        lines.forEach(next);
39    });
40    process.stdin.on('end', () => {
41        buf && next(buf);
42        gen.throw(new EOFError());
43    });
44}
45

1#include <algorithm> // copy
2#include <iostream> // cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <sstream> // istringstream
5#include <string> // getline, string
6#include <vector> // vector
7
8int find_min_rotated(std::vector<int> arr) {
9    int left = 0, right = arr.size() - 1, boundary_index = -1;
10    while (left <= right) {
11        int mid = left + (right - left) / 2;
12        // if arr[mid] <= last element, then it belongs to the lower half
13        if (arr[mid] <= arr[arr.size() - 1]) {
14            boundary_index = mid;
15            right = mid - 1;
16        } else {
17            left = mid + 1;
18        }
19    }
20    return boundary_index;
21}
22
23template<typename T>
24std::vector<T> get_words() {
25    std::string line;
26    std::getline(std::cin, line);
27    std::istringstream ss{line};
28    std::vector<T> v;
29    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
30    return v;
31}
32
33int main() {
34    std::vector<int> arr = get_words<int>();
35    int res = find_min_rotated(arr);
36    std::cout << res << '\n';
37}
38

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Line Sweep

Tree Traversal without Recursion

Greedy

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Find Minimum in Rotated Sorted Array

Try it yourself

Explanation