Floor in a Sorted Array Visualization & Animation

Finds the largest element ≤ target in a sorted array using binary search with a "last valid" tracker.

## What is it? Find the floor of a target in a sorted array — the largest element in the array that is less than or equal to the target. ## How it works - Binary search with a "last valid answer" tracker - If `arr[mid] <= target` → record `mid` as the current floor candidate; move `low = mid + 1` to search for a larger candidate - If `arr[mid] > target` → move `high = mid - 1` - Return the recorded candidate (or -1 if none found) ## When to use - Range queries: "find the largest value not exceeding X" - Closest element searches in sorted arrays - As a helper in interval/scheduling problems ## Key Points - "Floor" = largest element ≤ target - "Ceil" = smallest element ≥ target (symmetric) - O(log n) time, O(1) space - If target is smaller than all elements, floor does not exist (return -1 or indicate absence)

Category: algorithms

Difficulty: beginner

  • lower-upper-bound
  • binary-search

Time Complexity: O(log n)

Space Complexity: O(1)

Floor in a Sorted Array

beginner

Finds the largest element ≤ target in a sorted array using binary search with a "last valid" tracker.

GFG
PhaseInit
x5
Mid—
UB—
upper_bound(arr, x) = first i where arr[i] > xfloor = arr[upper_bound − 1]
lo
mid
hi
1
[0]
2
[1]
8
[2]
10
[3]
11
[4]
12
[5]
19
[6]
mid / UB
≤ x / floor
> x (too big)
search window
upper_bound approach: lo=0, hi=7 (half-open [lo, hi)). Find first index where arr[i] > x=5.