Floor and Ceil in Sorted Array in DSA Go - 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 or ceil of a number 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.

func floorCeil(arr []int, x int) (int, int) {
    low, high := 0, len(arr)-1
    floor, ceil := -1, -1
    for low <= high {
        mid := low + (high-low)/2
        if arr[mid] == x {
            return arr[mid], arr[mid]
        } else if arr[mid] < x {
            floor = arr[mid]
            low = mid + 1
        } else {
            ceil = arr[mid]
            high = mid - 1
        }
    }
    return floor, ceil
}

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 loop that halves the search space each time (binary search).
• How many times: The loop runs about log base 2 of n times, where n is the array size.

How Execution Grows With Input

Each step cuts the array 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 if the array gets very large.

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

Knowing how to use binary search to quickly find floor and ceil is a useful skill that shows you understand efficient searching.

Self-Check

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