← DiffPush

Implement lower bound

Baseline Binary Search · 1D Arrays O(log n) · O(1)

The Nearest Pickup Slot Below the Request

A warehouse picker works off a sorted list of aisle coordinates and receives a request coordinate that may fall between two slots. Fulfilment rules require the parcel to come from the deepest slot at or before the request coordinate. Identify that slot's position in the list, or report that no slot qualifies when the request sits before every coordinate.

Input: An integer n, an array arr of n distinct integers sorted in ascending order, and an integer x.

Output: The 0-indexed position of the largest element with value at most x, or -1 when every element exceeds x.

Constraints

• 1 <= n <= 10^5
• 1 <= arr[i] <= 10^6
• 0 <= x <= 10^6
• arr is sorted in ascending order with no duplicates

Examples

Example 1

Input: {"n":7,"arr":[1,2,8,10,11,12,19],"x":0}
Output: -1
Every slot coordinate exceeds 0, so no element qualifies as the floor and -1 is reported.

Example 2

Input: {"n":7,"arr":[1,2,8,10,11,12,19],"x":5}
Output: 1
The deepest coordinate not past 5 is 2, which sits at index 1.

Solve this in your browser →

Also on LeetCode ↗