Floor and Ceil in Sorted Array in DSA Javascript

Mental Model

Floor is the biggest number less than or equal to target; ceil is the smallest number greater than or equal to target in a sorted list.

Analogy: Imagine standing on a number line with sorted steps; floor is the step you stand on or just below, ceil is the step you stand on or just above.

Sorted Array: 1 -> 3 -> 5 -> 7 -> 9 -> null
Target: 6
Floor: 5 (just below 6)
Ceil: 7 (just above 6)

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target: 6

Goal: Find floor and ceil values for target 6 in the sorted array

Step 1: Start binary search with low=0, high=4

Array: [1, 3, 5, 7, 9]
low=0, high=4

Why: We begin searching the whole array to find floor and ceil

Step 2: Calculate mid = Math.floor((0+4)/2) = 2, check arr[mid]=5

mid=2, arr[mid]=5
low=0, high=4

Why: Check middle element to narrow search

Step 3: Since 5 < 6, update floor=5 and low=mid+1=3

floor=5
low=3, high=4

Why: 5 is less than target, so floor candidate updated, search right side for closer floor

Step 4: Calculate mid = Math.floor((3+4)/2) = 3, check arr[mid]=7

mid=3, arr[mid]=7
low=3, high=4

Why: Check middle element in right half

Step 5: Since 7 > 6, update ceil=7 and high=mid-1=2

ceil=7
low=3, high=2

Why: 7 is greater than target, so ceil candidate updated, search left side for closer ceil

Result:

Floor: 5
Ceil: 7

Annotated Code

DSA Javascript

class SortedArray {
  constructor(arr) {
    this.arr = arr;
  }

  floorAndCeil(target) {
    let low = 0;
    let high = this.arr.length - 1;
    let floor = null;
    let ceil = null;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      const val = this.arr[mid];

      if (val === target) {
        floor = val;
        ceil = val;
        break;
      } else if (val < target) {
        floor = val; // update floor candidate
        low = mid + 1; // search right side
      } else {
        ceil = val; // update ceil candidate
        high = mid - 1; // search left side
      }
    }

    return { floor, ceil };
  }
}

// Driver code
const arr = [1, 3, 5, 7, 9];
const target = 6;
const sortedArray = new SortedArray(arr);
const result = sortedArray.floorAndCeil(target);
console.log(`Floor: ${result.floor}`);
console.log(`Ceil: ${result.ceil}`);

while (low <= high) {

loop to narrow search range until low passes high

const mid = Math.floor((low + high) / 2);

calculate middle index to check

if (val === target) { floor = val; ceil = val; break; }

exact match found, floor and ceil are target

else if (val < target) { floor = val; low = mid + 1; }

update floor candidate and search right side

else { ceil = val; high = mid - 1; }

update ceil candidate and search left side

Output

Floor: 5

Ceil: 7

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Linear search would be O(n) by checking each element; binary search is faster for sorted arrays

Edge Cases

target smaller than all elements

floor remains null, ceil is the smallest element

DSA Javascript

let floor = null;

target larger than all elements

floor is the largest element, ceil remains null

DSA Javascript

let ceil = null;

target exactly matches an element

floor and ceil both equal target

DSA Javascript

if (val === target) { floor = val; ceil = val; break; }

When to Use This Pattern

When you need to find closest smaller or equal and closest larger or equal values in a sorted list, use binary search to find floor and ceil efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving search boundaries
Fix: Update floor when moving right (val < target), update ceil when moving left (val > target)

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a sorted array.

Use when you want quick lookup of nearest values around a target in sorted data.

The key is to update floor and ceil candidates while narrowing the search with binary search.