⬅ Previous Topic
Binary Search in Array using IterationNext Topic ⮕
Find Upper Bound in Sorted Array⬅ Previous Topic
Binary Search in Array using IterationNext Topic ⮕
Find Upper Bound in Sorted ArrayTopic Contents
Given a sorted array of integers and a target number x
, your task is to find the lower bound of x
.
x
.x
, return the array’s length.0
(default lower bound position).arr
and a target integer x
.low = 0
and high = arr.length - 1
.ans = arr.length
(in case x is greater than all elements).low ≤ high
:mid = Math.floor((low + high) / 2)
.arr[mid] ≥ x
, set ans = mid
and move high = mid - 1
.low = mid + 1
.ans
as the index of the lower bound.def lower_bound(arr, x):
low, high = 0, len(arr) - 1
ans = len(arr)
while low <= high:
mid = (low + high) // 2
if arr[mid] >= x:
ans = mid
high = mid - 1
else:
low = mid + 1
return ans
# Sample Input
arr = [1, 2, 4, 4, 5, 6]
x = 4
print("Lower Bound Index:", lower_bound(arr, x))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The lower bound is found at the very first mid index comparison in the binary search. |
Average Case | O(log n) | With each iteration, the binary search reduces the search space by half to locate the correct lower bound. |
Worst Case | O(log n) | The binary search may run until the search space is reduced to a single element when the target is not present or is larger than all elements. |
O(1)
Explanation: The algorithm operates in-place and uses a fixed number of variables (like low, high, mid, and ans), resulting in constant extra space usage.
⬅ Previous Topic
Binary Search in Array using IterationNext Topic ⮕
Find Upper Bound in 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.