Lower Bound in Sorted Array Binary Search Approach

Problem Statement❯

Given a sorted array of integers and a target number x, your task is to find the lower bound of x.

The lower bound is defined as the index of the first element in the array that is greater than or equal to x.
If all elements are smaller than x, return the array’s length.
If the array is empty, return 0 (default lower bound position).

Examples❯

Input Array	Key (x)	Lower Bound Index	Description
[10, 20, 30, 40, 50]	30	2	Exact match at index 2
[10, 20, 30, 40, 50]	35	3	First value ≥ 35 is 40 at index 3
[10, 20, 30, 40, 50]	5	0	All values ≥ 5, so index 0 is answer
[10, 20, 30, 40, 50]	60	5	No values ≥ 60, return array length 5
[10]	10	0	Single element equals key
[10]	5	0	Key smaller than only element
[10]	15	1	Key larger than only element
[]	10	0	Empty array, default lower bound is 0

Visualization Player

Solution❯

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.

Algorithm Steps❯

Given a sorted array arr and a target integer x.
Initialize two pointers: low = 0 and high = arr.length - 1.
Initialize ans = arr.length (in case x is greater than all elements).
Repeat while low ≤ high:
→ Calculate mid = Math.floor((low + high) / 2).
→ If arr[mid] ≥ x, set ans = mid and move high = mid - 1.
→ Else, move low = mid + 1.
Return ans as the index of the lower bound.

Code

Python

JavaScript

Java

C++

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))

Time Complexity❯

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.

Space Complexity❯

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 TopicBinary Search in Array using Iteration

Next Topic ⮕Find Upper Bound in Sorted Array