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.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The greatest element less than or equal to the number

B. The smallest element greater than or equal to the number

C. The average of all elements less than the number

D. The smallest element strictly less than the number

Solution

1. Step 1: Understand floor definition in sorted array

   The floor of a number is the greatest element in the array that is less than or equal to the given number.

2. Step 2: Compare with options

   The greatest element less than or equal to the number matches this definition exactly, while others describe ceil or incorrect concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option A

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor must be strictly less than number
• Mixing floor with average or median

2. Which of the following is the correct JavaScript syntax to find the floor of a number x in a sorted array arr using binary search?

easy

A. Use Math.floor(x) directly on array

B. Use a for loop from 0 to arr.length and return first element greater than x

C. Use arr.indexOf(x) to find floor

D. Use a while loop with start = 0, end = arr.length - 1, update mid and check arr[mid] <= x

Solution

1. Step 1: Understand binary search for floor

   Binary search uses start and end pointers, calculates mid, and checks if arr[mid] <= x to move start or end accordingly.

2. Step 2: Evaluate options

   Use a while loop with start = 0, end = arr.length - 1, update mid and check arr[mid] <= x correctly describes binary search logic for floor. Options A, B, and C are incorrect or irrelevant.

3. Final Answer:

   Use a while loop with start=0, end=arr.length-1, update mid and check arr[mid] ≤ x -> Option D

4. Quick Check:

   Binary search with arr[mid] ≤ x finds floor [OK]

Hint: Binary search with arr[mid] ≤ x finds floor efficiently [OK]

Common Mistakes:

• Using linear search instead of binary search
• Using indexOf which only finds exact matches
• Misusing Math.floor which works on numbers, not arrays

3. What is the output of the following JavaScript code?

const arr = [1, 3, 5, 7, 9];
function findFloor(arr, x) {
  let start = 0, end = arr.length - 1, floor = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] <= x) {
      floor = arr[mid];
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return floor;
}
console.log(findFloor(arr, 6));

medium

A. 6

B. 5

C. 7

D. -1

Solution

1. Step 1: Trace binary search for floor of 6

   Initial start=0, end=4, floor=-1. mid=2 (arr[2]=5) ≤ 6, floor=5, start=3. mid=3 (arr[3]=7) > 6, end=2. Loop ends.

2. Step 2: Return floor value

   Floor found is 5, which is the greatest element ≤ 6.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Floor of 6 in [1,3,5,7,9] is 5 [OK]

Hint: Floor is last arr[mid] ≤ x during binary search [OK]

Common Mistakes:

• Returning mid index instead of value
• Confusing floor with ceil
• Not updating floor variable correctly

4. Identify the bug in this JavaScript function to find the ceil of a number x in a sorted array arr:

function findCeil(arr, x) {
  let start = 0, end = arr.length - 1, ceil = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] >= x) {
      ceil = arr[mid];
      end = mid + 1;
    } else {
      start = mid + 1;
    }
  }
  return ceil;
}

medium

A. The line end = mid + 1; should be end = mid - 1;

B. The line start = mid + 1; should be start = mid - 1;

C. The initial value of ceil should be 0 instead of -1

D. The while loop condition should be start < end instead of start <= end

Solution

1. Step 1: Analyze binary search update for ceil

   When arr[mid] ≥ x, we update ceil and must move end to mid - 1 to search left side for smaller ceil.

2. Step 2: Identify incorrect update

   The code incorrectly sets end = mid + 1, which moves end right, causing infinite loop or wrong result.

3. Final Answer:

   The line end = mid + 1; should be end = mid - 1; -> Option A

4. Quick Check:

   For ceil, move end left with end = mid - 1 [OK]

Hint: For ceil, move end left; for floor, move start right [OK]

Common Mistakes:

• Moving end pointer in wrong direction
• Confusing ceil logic with floor
• Incorrect initial ceil value

5. Given a sorted array arr = [2, 4, 6, 8, 10], write a function to find both floor and ceil of a number x. What will be the floor and ceil of x = 5?

hard

A. Floor = 5, Ceil = 5

B. Floor = 6, Ceil = 4

C. Floor = 4, Ceil = 6

D. Floor = 2, Ceil = 10

Solution

1. Step 1: Understand floor and ceil definitions

   Floor is greatest element ≤ x, ceil is smallest element ≥ x.

2. Step 2: Find floor and ceil for x=5 in arr

   Elements ≤ 5 are 2 and 4; greatest is 4 (floor). Elements ≥ 5 are 6, 8, 10; smallest is 6 (ceil).

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option C

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ x max, Ceil ≥ x min in sorted array [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals x if not present
• Choosing wrong boundary elements