Solution: Find the Floor and Ceil of a Number in a Sorted Array

Solution 1

The naive approach to this problem would be:

1. Traverse the array starting from the 0th index to the last index.
2. Compare value at each index arr[i] with the given input integer $x$.
3. When you reach the maximum value lesser than equal to $x$, store it as the $floor$ value.
4. Similarly, the minimum value greater than equal to $x$ will be stored as $ceiling$ value while you linearly traverse the array.
5. Terminate the traversal when you reach the end of the array.

Time complexity

Since the loop iterates every single element at least once, the running complexity for this solution would be $O(n)$, where $n$ is the size of the array.