Find Minimum in Rotated Sorted Array

mediumBinary Search+20 XPTime limit 2s

A sorted array of distinct values was rotated: some prefix was moved to the end (for example 0 1 2 4 5 6 7 → 4 5 6 7 0 1 2). It may also be rotated by zero. Find the minimum value.

Input:

line 1: n
line 2: n distinct integers

Output: the minimum value.

Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴. Aim for O(log n).

Think about it: compare a[mid] with a[high]. If a[mid] > a[high], the drop (and the minimum) is to the right of mid.

Sample input 1

5
3 4 5 1 2

Sample output 1

Sample input 2

7
4 5 6 7 0 1 2

Sample output 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…