To find the lower bound of a number x
in a sorted array, we want to locate the first element that is greater than or equal to x
. Binary search is the ideal approach for this because it efficiently narrows the range to find this position without scanning every element.
Understanding Lower Bound
Let’s understand it through a few common scenarios:
- If
x
exists in the array, the lower bound is the index of its first occurrence.
- If
x
is smaller than all elements, the lower bound is 0
.
- If
x
is greater than all elements, there's no valid element ≥ x
, so the lower bound is the length of the array.
- If the array is empty, the result is naturally
0
, since there's nowhere to insert the element.
How Binary Search Helps
Binary search helps us find the lower bound efficiently by:
- Maintaining two pointers:
low
and high
, covering the current search range.
- If we find
arr[mid] ≥ x
, it could be a valid answer, but we still check the left half to find a better one.
- If
arr[mid] < x
, we discard the left half and move to the right.
We continue until all positions are checked. The moment we find an element ≥ x
, we store its index as a possible lower bound. Eventually, we return the smallest index that satisfies the condition.
Why This is Useful
Lower bound is useful in range queries, insert positions, and understanding element distributions. Using binary search keeps the time complexity at O(log n), which is essential for large datasets.