Search in Rotated Sorted Array

Medium

binary-searcharray

A sorted array of distinct integers was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated array nums and a target, return its index or -1, in O(log n).

Input

Line 1: space-separated integers (rotated sorted, distinct)
Line 2: integer target

Output: the index, or -1.

Example 1

Input:

4 5 6 7 0 1 2
0

Output:

Example 2

Input:

4 5 6 7 0 1 2
3

Output:

-1

Constraints

1 ≤ nums.length ≤ 5000
Distinct values.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Search in Rotated Sorted Array

Medium

binary-searcharray

Input

Line 1: space-separated integers (rotated sorted, distinct)
Line 2: integer target

Output: the index, or -1.

Example 1

Input:

4 5 6 7 0 1 2
0

Output:

Example 2

Input:

4 5 6 7 0 1 2
3

Output:

-1

Constraints

1 ≤ nums.length ≤ 5000
Distinct values.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.