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❯

Step-by-Step Solution to Find the Lower Bound of a Number in a Sorted Array

Understanding the Problem

We are given a sorted array and a number x. Our task is to find the lower bound of x in the array.

The lower bound is defined as the index of the first element in the array that is greater than or equal to x.

Let’s Understand With an Example

arr = [1, 3, 3, 5, 8, 9]
x = 4

We want to find the first number in the array that is ≥ 4. Let's look at the array:

1 < 4 → Not valid
3 < 4 → Not valid
3 < 4 → Not valid
5 ≥ 4 → Valid, and it's the first one

So the lower bound index is 3 (0-based).

Approach: Using Binary Search

We will use binary search to solve this efficiently. Here’s the intuition:

Binary search helps narrow down the location quickly in O(log n) time.
We maintain two pointers: low and high.
We calculate the middle index: mid = (low + high) / 2.
If arr[mid] ≥ x, it could be our answer, but there may be a better one to the left, so we move high = mid - 1.
If arr[mid] < x, we move low = mid + 1.

The final answer will be at index low, which will point to the smallest element ≥ x.

Edge Cases to Consider

x is smaller than all elements: The lower bound will be at index 0.
x is larger than all elements: The lower bound does not exist within the array, so the answer will be the array's length.
x exists multiple times: The lower bound is the index of its first occurrence.
The array is empty: There is nowhere to insert, so the lower bound is 0.

Finally

Finding the lower bound is helpful in many real-world applications such as range-based queries, inserting into sorted arrays, and understanding how values are distributed in a dataset.

Using binary search allows us to solve the problem quickly and efficiently, even for large arrays.

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

Comments

Loading comments...