Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Binary Search

Minimum in Rotated Sorted Array

Medium · Binary Search · Asked at Amazon, Microsoft, Google, Meta

A sorted array of distinct values was rotated at an unknown point (e.g. [3,4,5,1,2]). Print its minimum element in O(log n).

Input

First line: n. Second line: n space-separated integers.

Output

The minimum value.

Constraints

Compare a[mid] with a[high]: if a[mid] > a[high], the minimum is to the right of mid; otherwise it is at mid or to its left.

Example 1

Input

5
3 4 5 1 2

Output

1

Example 2

Input

4
11 13 15 17

Output

11

Hints

  1. Compare the middle element with the last element of the current range.
  2. If a[mid] > a[hi], the drop (and the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.

Approach

Binary search with lo = 0, hi = n − 1. While lo < hi: if a[mid] > a[hi], the rotation point is after mid, so lo = mid + 1; otherwise [mid, hi] is sorted and the minimum is at mid or before, so hi = mid. When they meet, a[lo] is the minimum. Comparing with a[hi] (not a[lo]) also handles arrays that are not rotated at all.

Complexity: O(log n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] > a[hi]) lo = mid + 1;
        else hi = mid;
    }
    cout << a[lo] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1:]
lo, hi = 0, len(a) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] > a[hi]:
        lo = mid + 1
    else:
        hi = mid
print(a[lo])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (a[mid] > a[hi]) lo = mid + 1;
            else hi = mid;
        }
        System.out.println(a[lo]);
    }
}

Solve Minimum in Rotated Sorted Array online · All practice problems