Find a Local Minimum with Left-Biased Binary Search
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `left_biased_local_min(values)` for a nonempty integer array.
An index is a local minimum when its value is no greater than each neighbor that exists. Return the index produced by this deterministic binary-search rule:
1. Start with `left = 0` and `right = len(values) - 1`.
2. While `left < right`, let `mid = left + (right - left) // 2`.
3. If `values[mid] > values[mid + 1]`, set `left = mid + 1`; otherwise set `right = mid`.
4. Return the converged index.
The equality case deliberately keeps the left half, so adjacent duplicate values are supported and the result is deterministic. The returned index is a local minimum under the non-strict definition above.
```hint Follow a non-increasing direction
When the value drops from `mid` to `mid + 1`, the right interval contains a local minimum; otherwise the left interval, including `mid`, contains one.
```
```hint Endpoints need only one comparison
Index zero or the final index can be a valid local minimum because only an existing neighbor matters.
```
Quick Answer: Find a deterministic local-minimum index in a nonempty integer array with a left-biased binary search. Understand why the equality case preserves the left interval and how endpoints and duplicates satisfy the non-strict definition.
Implement left_biased_local_min(values) for a nonempty integer array. Repeatedly compare the midpoint with its right neighbor, moving right only when the midpoint is larger and otherwise keeping the left half; return the converged index.
Constraints
- 1 <= values.length <= 4,096.
- Each value is between -1,000,000,000 and 1,000,000,000.
- A local minimum is no greater than each neighbor that exists, and equality must keep the left half.
Examples
Input: ([3, 2, 1, 2, 3],)
Expected Output: 2
Input: ([2, 1, 1, 2],)
Expected Output: 1
Hints
- A drop from middle to middle + 1 guarantees that the right interval contains a local minimum.
- When the pair is flat or rising, retain middle by assigning right = middle to preserve the required left bias.