Search a Rotated Sorted Array in One Binary-Search Pass
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Search a Rotated Sorted Array in One Binary-Search Pass
### Problem
Implement `searchRotated(values, target) -> index`.
`values` was formed by taking a strictly increasing array of distinct integers and rotating it at an unknown position. Return the zero-based index of `target`, or `-1` when `target` is absent.
Use one binary-search loop. Do not first locate the rotation point and then run a second binary search. Return immediately when the target is found.
### Portable Contract
- `values` is an integer array with `0 <= values.length <= 12,000`.
- All values are distinct and each is between `-1,000,000,000` and `1,000,000,000`.
- `target` is an integer in the same range.
- An empty array returns `-1`. An unrotated strictly increasing array is valid.
- Do not modify `values`.
- Let `B` be the compact UTF-8 JSON byte length of `[values,target]`, counting every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 96,000`; the serialized integer result adds at most five bytes.
- Target `O(log n)` time and `O(1)` auxiliary space for `n = values.length`.
All four languages use one integer array and one integer scalar, returning an integer: `list[int]` in Python, arrays in JavaScript, `List<Integer>` in Java, and `vector<int>` in C++.
```hint Identify the ordered half
At every iteration, at least one side of the midpoint is still in ordinary increasing order.
```
```hint Keep the interval invariant precise
Use comparisons that decide whether the target lies inside the ordered half before discarding it, and compute the midpoint from the interval width.
```
### Examples
```text
values = [4, 5, 6, 7, 0, 1, 2]
target = 0
index = 4
```
```text
values = [4, 5, 6, 7, 0, 1, 2]
target = 3
index = -1
```
```text
values = []
target = 8
index = -1
```
### Discussion Requirements
- State the invariant that keeps the target, when present, inside the current search interval.
- Explain how distinct values let the algorithm determine which half is ordered.
- Use an overflow-safe midpoint expression such as `low + (high - low) / 2` in fixed-width languages.
- Test an unrotated array, rotations at both ends, one element, an absent target, and an empty array.
Quick Answer: Search for a target in a rotated strictly increasing array using one binary-search pass. The exercise focuses on interval invariants, identifying an ordered side, handling absent and boundary cases, and achieving logarithmic time without modifying the input.
Implement `searchRotated(values, target) -> index`.
`values` was formed by taking a strictly increasing array of distinct integers
and rotating it left at an unknown position. The rotation amount may be zero, so
an already-sorted array is a valid input. Return the zero-based index of
`target` in `values`, or `-1` when `target` does not appear.
Use a single binary-search loop. Do not first locate the rotation point with one
search and then run a second binary search over a chosen half, and return as
soon as the target is found rather than recording an index and continuing. Do
not modify `values`.
### Output semantics
The answer is a single integer. Because every element of `values` is distinct, a
present target occupies exactly one index, so the correct answer is unique: the
index `i` with `values[i] == target`, or `-1` when no such `i` exists. No
ordering or tie-breaking rule is needed.
### Constraints
- `0 <= len(values) <= 12000`.
- All elements of `values` are distinct, and `-1000000000 <= values[i] <= 1000000000`.
- `target` is an integer with `-1000000000 <= target <= 1000000000`.
- `values` is a left rotation (possibly by zero) of a strictly increasing array.
- An empty `values` returns `-1`.
- Let `B` be the compact UTF-8 JSON byte length of `[values, target]`, counting
every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 96000`.
- Every value and every index fits in a signed 32-bit integer, so `int` is
sufficient in Java and C++; still compute the midpoint as
`low + (high - low) / 2` rather than `(low + high) / 2`.
- Target `O(log n)` time and `O(1)` auxiliary space for `n = len(values)`.
### Examples
Example 1:
values = [4, 5, 6, 7, 0, 1, 2]
target = 0
returns 4
`0` sits in the rotated tail. The first midpoint is `values[3] == 7`; the left
half `[4, 5, 6, 7]` is ordered and `0` is not inside `[4, 7)`, so the search
discards it and continues in `[0, 1, 2]`, finding `0` at index 4.
Example 2:
values = [4, 5, 6, 7, 0, 1, 2]
target = 3
returns -1
`3` lies numerically between the array's maximum `7` and its minimum `0`, in the
gap created by the rotation, so it is absent and the loop exhausts the interval.
Example 3:
values = []
target = 8
returns -1
### Language shapes
`values` is `list[int]` in Python, an array of numbers in JavaScript,
`java.util.List<Integer>` in Java, and `const std::vector<int>&` in C++.
`target` is an integer scalar and the return value is an integer in all four.
Constraints
- 0 <= len(values) <= 12000
- -1000000000 <= values[i] <= 1000000000
- all elements of values are distinct
- -1000000000 <= target <= 1000000000
- values is a left rotation (possibly by zero) of a strictly increasing array
- an empty values returns -1
- B <= 96000, where B is the compact UTF-8 JSON byte length of [values, target]
- every value and every index fits in a signed 32-bit integer
- required: O(log n) time and O(1) auxiliary space, in a single binary-search loop
Examples
Input: ([4,5,6,7,0,1,2],0)
Expected Output: 4
Input: ([4,5,6,7,0,1,2],3)
Expected Output: -1
Hints
- Split the interval at its midpoint and ask which side is still in plain ascending order. A single rotation creates exactly one descent, so that descent can sit on only one side.
- Comparing values[low] with values[mid] tells you which side is ordered. Distinctness is what makes that comparison decisive.
- Once you know the ordered side, a range test on its two endpoints decides whether the target is inside it. Watch which endpoint is inclusive: the midpoint has already been tested for equality.