Floor and Ceil in Sorted Array in DSA Javascript - Time & Space Complexity

Time Complexity: Floor and Ceil in Sorted Array

O(log n)

Understanding Time Complexity

We want to know how fast we can find the floor and ceil values in a sorted array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function floorAndCeil(arr, x) {
  let left = 0, right = arr.length - 1;
  let floor = -1, ceil = -1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === x) {
      floor = arr[mid];
      ceil = arr[mid];
      break;
    } else if (arr[mid] < x) {
      floor = arr[mid];
      left = mid + 1;
    } else {
      ceil = arr[mid];
      right = mid - 1;
    }
  }
  return { floor, ceil };
}
    

This code finds the floor (largest value ≤ x) and ceil (smallest value ≥ x) in a sorted array using binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search space each time.
• How many times: About log base 2 of n times, where n is the array length.

How Execution Grows With Input

Each step cuts the array size roughly in half, so the number of steps grows slowly as the array grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one more step.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find floor and ceil grows slowly, even for large arrays.

Common Mistake

[X] Wrong: "Since we check elements one by one, it takes O(n) time."

[OK] Correct: The code uses binary search, which skips many elements each step, so it does not check all elements.

Interview Connect

Understanding this helps you quickly find values in sorted data, a common task in coding challenges and real projects.

Self-Check

"What if the array was not sorted? How would the time complexity change?"