Floor and Ceil in Sorted Array in DSA C++ - 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.

int floorCeil(const vector<int>& arr, int x, int& floorVal, int& ceilVal) {
    int low = 0, high = arr.size() - 1;
    floorVal = -1; ceilVal = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            floorVal = ceilVal = arr[mid];
            return mid;
        } else if (arr[mid] < x) {
            floorVal = arr[mid];
            low = mid + 1;
        } else {
            ceilVal = arr[mid];
            high = mid - 1;
        }
    }
    return -1;
}
    

This code finds the floor and ceil of 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 range each time.
• How many times: The loop runs about log₂(n) times, where n is the array size.

How Execution Grows With Input

Each step cuts the search area 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 extra 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 half the array each step, so it doesn't check every element.

Interview Connect

Knowing how to quickly find floor and ceil using binary search shows you understand efficient searching, a key skill in many coding problems.

Self-Check

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