⬅ Previous Topic
Search Insert Position in Sorted Array (Lower Bound Approach)Next Topic ⮕
First Occurrence in a Sorted Array⬅ Previous Topic
Search Insert Position in Sorted Array (Lower Bound Approach)Next Topic ⮕
First Occurrence in a Sorted ArrayTopic Contents
Given a sorted array of integers and a target number x
, your task is to find the floor and ceil of x
in the array.
x
is the greatest number in the array that is less than or equal to x
.x
is the smallest number in the array that is greater than or equal to x
.If the floor or ceil does not exist, return -1
for that value.
arr
and a target value x
.floor = -1
and ceil = -1
.low ≤ high
, compute mid
.arr[mid] == x
, both floor and ceil are arr[mid]
. Return.arr[mid] < x
, update floor = arr[mid]
, search right.arr[mid] > x
, update ceil = arr[mid]
, search left.floor
and ceil
.def find_floor_ceil(arr, x):
low, high = 0, len(arr) - 1
floor, ceil = -1, -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
# Exact match is both floor and ceil
return arr[mid], arr[mid]
elif arr[mid] < x:
# Current element could be a candidate for floor
floor = arr[mid]
low = mid + 1 # Search in the right half
else:
# Current element could be a candidate for ceil
ceil = arr[mid]
high = mid - 1 # Search in the left half
return floor, ceil
# Sample Input
arr = [1, 2, 4, 6, 10, 12]
x = 5
print("Floor and Ceil:", find_floor_ceil(arr, x))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The target value is found at the mid index during the first iteration of binary search, requiring no further comparisons. |
Average Case | O(log n) | The binary search halves the search space in each step until the correct floor and ceiling values are found. |
Worst Case | O(log n) | In the worst case, the search continues until only one element remains, after which the floor and ceiling values are determined. |
O(1)
Explanation: The algorithm operates using a constant number of variables (like low, high, mid, floor, ceil), without requiring additional memory.
⬅ Previous Topic
Search Insert Position in Sorted Array (Lower Bound Approach)Next Topic ⮕
First Occurrence in a Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.