Find Minimum in Rotated Sorted Array

Binary Search

Given a rotated sorted array of distinct integers, return its minimum element. Must run in O(log n).

Examples

Example 1

Input

nums

3

4

5

1

2

target1

Output

1

Constraints

1 ≤ nums.length ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All the integers of nums are unique.
nums is sorted in ascending order and rotated between 1 and n times.

Stuck? Hint 1

Compare arr[mid] with arr[hi] to decide which half holds the minimum.

Editorial· Binary search against the right end

Rotating a sorted array cuts it in two and swaps the halves. What you get is two climbing runs side by side. In [3,4,5,1,2] they are 3,4,5 and 1,2. Every value in the left run is bigger than every value in the right run, because the left run used to be the top of the sorted order. The minimum is the first value of the right run.

Time O(log n)Space O(1)

The full walkthrough and code are part of Premium

Input

3

4

5

1

2

target1

Expected Output

Ctrl / ⌘ + Enter

Find Minimum in Rotated Sorted Array

Binary Search

Given a rotated sorted array of distinct integers, return its minimum element. Must run in O(log n).

Examples

Example 1

Input

nums

3

4

5

1

2

target1

Output

1

Constraints

1 ≤ nums.length ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All the integers of nums are unique.
nums is sorted in ascending order and rotated between 1 and n times.

Stuck? Hint 1

Compare arr[mid] with arr[hi] to decide which half holds the minimum.

Editorial· Binary search against the right end

Rotating a sorted array cuts it in two and swaps the halves. What you get is two climbing runs side by side. In [3,4,5,1,2] they are 3,4,5 and 1,2. Every value in the left run is bigger than every value in the right run, because the left run used to be the top of the sorted order. The minimum is the first value of the right run.

Time O(log n)Space O(1)

The full walkthrough and code are part of Premium

Input

3

4

5

1

2

target1

Expected Output

Ctrl / ⌘ + Enter