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.
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 because 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 to 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 feasible function 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 First True in a Sorted Boolean Array module.
Time Complexity: O(log(n))
Space Complexity: O(1)
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)
221import 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}
361using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int FindMinRotated(List<int> arr)
8 {
9 int left = 0;
10 int right = arr.Count - 1;
11 int boundaryIndex = -1;
12 while (left <= right)
13 {
14 int mid = left + (right - left) / 2;
15 if (arr[mid] <= arr[arr.Count - 1])
16 {
17 boundaryIndex = mid;
18 right = mid - 1;
19 }
20 else
21 {
22 left = mid + 1;
23 }
24 }
25 return boundaryIndex;
26 }
27
28 public static List<string> SplitWords(string s)
29 {
30 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
31 }
32
33 public static void Main()
34 {
35 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
36 int res = FindMinRotated(arr);
37 Console.WriteLine(res);
38 }
39}
401"use strict";
2
3function findMinRotated(arr) {
4 let left = 0;
5 let right = arr.length - 1;
6 let boundaryIndex = -1;
7 while (left <= right) {
8 const mid = left + Math.floor((right - left) / 2);
9 // if <= last element, then belongs to lower half
10 if (arr[mid] <= arr[arr.length - 1]) {
11 boundaryIndex = mid;
12 right = mid - 1;
13 } else {
14 left = mid + 1;
15 }
16 }
17 return boundaryIndex;
18}
19
20function splitWords(s) {
21 return s === "" ? [] : s.split(" ");
22}
23
24function* main() {
25 const arr = splitWords(yield).map((v) => parseInt(v));
26 const res = findMinRotated(arr);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line) => gen.next(line).done && process.exit();
34 let buf = "";
35 next();
36 process.stdin.setEncoding("utf8");
37 process.stdin.on("data", (data) => {
38 const lines = (buf + data).split("\n");
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on("end", () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
471#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int find_min_rotated(std::vector<int> arr) {
9 int left = 0;
10 int right = arr.size() - 1;
11 int boundary_index = -1;
12 while (left <= right) {
13 int mid = left + (right - left) / 2;
14 // if arr[mid] <= last element, then it belongs to the lower half
15 if (arr[mid] <= arr[arr.size() - 1]) {
16 boundary_index = mid;
17 right = mid - 1;
18 } else {
19 left = mid + 1;
20 }
21 }
22 return boundary_index;
23}
24
25template<typename T>
26std::vector<T> get_words() {
27 std::string line;
28 std::getline(std::cin, line);
29 std::istringstream ss{line};
30 ss >> std::boolalpha;
31 std::vector<T> v;
32 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
33 return v;
34}
35
36int main() {
37 std::vector<int> arr = get_words<int>();
38 int res = find_min_rotated(arr);
39 std::cout << res << '\n';
40}
411package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9)
10
11func findMinRotated(arr []int) int {
12 left, right := 0, len(arr)-1
13 boundaryIndex := -1
14
15 for left <= right {
16 mid := (left + right) / 2
17 // if <= last element, then belongs to lower half
18 if arr[mid] <= arr[len(arr)-1] {
19 boundaryIndex = mid
20 right = mid - 1
21 } else {
22 left = mid + 1
23 }
24 }
25
26 return boundaryIndex
27}
28
29func arrayAtoi(arr []string) []int {
30 res := []int{}
31 for _, x := range arr {
32 v, _ := strconv.Atoi(x)
33 res = append(res, v)
34 }
35 return res
36}
37
38func splitWords(s string) []string {
39 if s == "" {
40 return []string{}
41 }
42 return strings.Split(s, " ")
43}
44
45func main() {
46 scanner := bufio.NewScanner(os.Stdin)
47 scanner.Scan()
48 arr := arrayAtoi(splitWords(scanner.Text()))
49 res := findMinRotated(arr)
50 fmt.Println(res)
51}
52