Baseline Binary Search · 1D Arrays O(n log n) · O(1)
A lab calibrator compares a probe reading against a reference chart, but the chart was compiled from several technicians and its entries are out of order. The calibration needs two anchors: the closest reference value at or below the reading and the closest one at or above it. Bring the chart into order first, then locate both anchors, using -1 whenever an anchor does not exist.
Input: An integer n, an array arr of n integers in arbitrary order, and an integer x.
Output: A pair [floor, ceil] of values: floor is the largest element at most x (or -1 if x is below every element) and ceil is the smallest element at least x (or -1 if x is above every element).
1 <= n <= 10^51 <= arr[i] <= 10^61 <= x <= 10^6Input: {"n":8,"arr":[5,6,8,9,6,5,5,6],"x":7}
Output: [6,8]
After ordering the chart, 6 is the deepest value not past 7 and 8 is the shallowest value not below it.
Input: {"n":8,"arr":[5,6,8,9,6,5,5,6],"x":8}
Output: [8,8]
The reading matches a reference exactly, so both anchors collapse onto the same value 8.