Search a Rotated Increasing Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You receive an integer array `values` and an integer `key`. The array was originally in strictly increasing order. It may have been left unchanged, or it may have been left rotated at an unknown split position `r`, where `1 <= r < n` and `n` is the array length.
A left rotation places the entries from position `r` through the end first, followed by the entries from position `0` through `r - 1`. The order within each of these two parts stays the same.
Return the zero-based index of `key` in the array you receive. Return `-1` if `key` does not occur in it. All array values are distinct.
Your algorithm must run in `O(log n)` time.
### Examples
**Example 1**
```text
Input: values = [9,14,21,-7,-2,3], key = -2
Output: 4
```
The array is a rotation of `[-7,-2,3,9,14,21]`. In the received array, `-2` is at index `4`.
**Example 2**
```text
Input: values = [2,5,11], key = 6
Output: -1
```
This array has not been rotated, and it does not contain `6`.
### Constraints
- `1 <= values.length <= 5000`
- `-10^4 <= values[i] <= 10^4`
- Every value in `values` is unique.
- `values` can be obtained by applying zero or one left rotation to a strictly increasing array.
- `-10^4 <= key <= 10^4`
Overview: Find a value's index in a rotated sorted array of distinct integers in logarithmic time, returning -1 when it is absent.
