You are given an array arr of integers sorted in non-decreasing order, and an integer x.
Return the 0-based index of the largest element in arr that is less than or equal to x. This element is called the floor of x in arr. If no element of arr is less than or equal to x, return -1.
Note: if the floor value occurs multiple times in arr, return the index of its last occurrence.
x must live?<= x sits in a prefix of the array — the answer is simply the index where that prefix ends.arr[mid] <= x, record mid as a candidate and move right; otherwise move left. The last recorded candidate is the answer.arr[mid] <= x, the search keeps chasing later qualifying indices and settles on the last one.<= x, so there is no floor — return -1. This is why ans starts at -1 and is only overwritten when a qualifying element is found.<= x — it equals x only when x itself appears in the array. For x = 5 in [1, 2, 8], the floor is 2.arr[i] >= x — on arr[mid] >= x record the candidate and move left, otherwise move right. Same skeleton, flipped comparison.O(log n) overall.O(log n) per query versus O(n) for a scan. With 10^6 elements that is about 20 probes per query instead of up to a million.arr[i] <= x is exactly one position before the first index with arr[i] > x — which is what C++'s upper_bound computes.floor(2.7) = 2 is the greatest integer not exceeding 2.7, the array floor is the greatest element not exceeding x.Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 5 Output: 1 The largest element <= 5 is 2, at index 1.
Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 11 Output: 4 The largest element <= 11 is 10, which appears at indices 3 and 4. The last occurrence is at index 4.
Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 0 Output: -1 No element is <= 0, so there is no floor.
- 1 <= arr.size <= 10^6 - 1 <= arr[i] <= 10^6 - 0 <= x <= 10^6 - arr is sorted in non-decreasing order
This problem looks tiny, but it hides the single most reused binary-search pattern in interviews: find the boundary. Master it here and lower bound, upper bound, first/last occurrence, and search-insert-position all fall out of the same skeleton.
i is at most arr[i] — one comparison tells you about a whole half.lo, hi, and mid — here adapted from find a value to find a boundary.Formally: given a non-decreasing array arr and an integer x, return the 0-based index of the largest element <= x. If that value occurs more than once, return the index of its last occurrence; if no element is <= x, return -1.
Worked example — arr = [1, 2, 8, 10, 10, 12, 19], x = 11
index: 0 1 2 3 4 5 6
value: 1 2 8 10 10 12 19
Y Y Y Y Y N N (Y = value <= 11)
^
last Y is index 4 -> answer 4
Everything <= x forms a prefix of the array; the answer is where that prefix ends.
Two or three sharp questions before coding tell the interviewer you think about contracts, not just code.
“Is the array guaranteed to be sorted, and in which direction?”
The entire approach rests on non-decreasing order — on a descending array the same code silently returns wrong indices.
“Can the array contain duplicates?”
Yes — and then the tie rule kicks in: return the last occurrence of the floor value.
“What should I return if every element is greater than x?”
Return -1 — there is no floor. This is the case where x is smaller than arr[0].
“If x itself is present in the array, is it its own floor?”
Yes — floor means less than or equal, so an exact match qualifies (last occurrence if repeated).
“How large can the array get?”
Up to 10^6 elements — a linear scan survives one query, but the sorted guarantee is an open invitation to O(log n) binary search.
Before I code, I want to confirm the array is sorted in non-decreasing order and may contain duplicates.
If the floor value repeats, I will return the index of its last occurrence.
And if x is smaller than the first element, I will return -1 since no floor exists.
Because arr is sorted, the predicate arr[i] <= x is monotone: true, true, …, true, then false forever. All qualifying elements are bunched at the front, so the answer is simply the index where the true-block ends.
arr: [ <=x | <=x | <=x | >x | >x ]
^
answer = last trueProbe the middle. If arr[mid] <= x, then mid qualifies — remember it and look right for an even later qualifying index. If arr[mid] > x, the boundary lies strictly to the left. Either way half the array disappears per step: O(log n).
By moving right whenever arr[mid] <= x, the search keeps chasing later qualifying indices — so among equal floor values it naturally settles on the last occurrence. No special-case code needed.
| Linear scan | Boundary binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Uses sortedness | Only to stop early | Fully |
Full code for both approaches lives in the Approaches selector below.
Key takeaway
When a sorted array asks for the last element satisfying a monotone condition, run boundary binary search: on success record the index and go right, on failure go left. The same skeleton solves floor, ceiling, first/last occurrence, and search-insert-position.
lo = 0, hi = n - 1, ans = -1
while lo <= hi:
mid = lo + (hi - lo) / 2
if arr[mid] <= x: ans = mid, lo = mid + 1 # candidate — look right
else: hi = mid - 1 # too big — look left
return ans