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)
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}
401function 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}
451#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