Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Implement Lower Bound

EASYProblemSolveExternal Links

Description

Given a sorted array arr[] and a number target, find the lower bound of the target in this given array.

The lower bound of a number is defined as the smallest index in the sorted array where the element is greater than or equal to the given number.

Note: If all the elements in the given array are smaller than the target, the lower bound will be the length of the array.

Examples

Example 1

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 9

Output: 3

Explanation: Index 3 is the smallest index where arr[3] = 10, which is greater than or equal to 9.

Example 2

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 11

Output: 4

Explanation: Index 4 is the smallest index where arr[4] = 11, which is greater than or equal to 11. Note that arr[3] = 10 is less than 11, so index 3 does not qualify. Even though arr[5] = 11 also equals the target, index 4 comes first.

Example 3

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 100

Output: 7

Explanation: No element in the array is greater than or equal to 100. In this case, the lower bound is defined as the length of the array, which is 7.

Example 4

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 2

Output: 0

Explanation: The very first element arr[0] = 2 is already greater than or equal to 2, so the lower bound is index 0.

Constraints

  • 1 ≤ arr.size() ≤ 10^6
  • 1 ≤ arr[i] ≤ 10^6
  • 1 ≤ target ≤ 10^6
  • The array arr is sorted in non-decreasing order.

Editorial

Brute Force - Linear Search

Intuition

The simplest way to find the lower bound is to scan through the array from left to right and find the first element that is greater than or equal to the target.

Since the array is sorted in non-decreasing order, once we find an element that satisfies arr[i] >= target, we know that all subsequent elements will also be ≥ target (because they are at least as large). Therefore, the very first such element we encounter gives us the lower bound.

Think of it like walking down a sorted row of numbered boxes. You start from the left and check each box: "Is this number at least as big as what I'm looking for?" The moment you say "yes", you stop — that box's position is the lower bound.

Step-by-Step Explanation

Let's trace through with arr = [2, 3, 7, 10, 11, 11, 25], target = 9:

Step 1: Check i = 0: arr[0] = 2. Is 2 ≥ 9? No. Move on.

Step 2: Check i = 1: arr[1] = 3. Is 3 ≥ 9? No. Move on.

Step 3: Check i = 2: arr[2] = 7. Is 7 ≥ 9? No. Move on.

Step 4: Check i = 3: arr[3] = 10. Is 10 ≥ 9? Yes! Return index 3.

We checked 4 elements. In the worst case (target = 100), we would check all 7 elements and return 7 (the array length).

Linear Search for Lower Bound — Scan left to right, checking each element against the target until we find the first one that is ≥ target.

Algorithm

  1. Iterate through the array from index 0 to n - 1.
  2. At each index i, check if arr[i] >= target.
  3. If yes, return i — this is the lower bound.
  4. If the loop completes without finding such an element, return n (the length of the array).

Code

#include <vector>
using namespace std;

class Solution {
public:
    int lowerBound(vector<int>& arr, int target) {
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            if (arr[i] >= target) {
                return i;
            }
        }
        return n;
    }
};
class Solution:
    def lowerBound(self, arr: list[int], target: int) -> int:
        n = len(arr)
        for i in range(n):
            if arr[i] >= target:
                return i
        return n
class Solution {
    public int lowerBound(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] >= target) {
                return i;
            }
        }
        return n;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (when the target is larger than all elements), we scan the entire array. On average, we scan roughly half the array. Either way, the time grows linearly with the array size.

For n = 10^6, this means up to 1 million comparisons per query. This is acceptable for a single query but wasteful when we have the sorted property available.

Space Complexity: O(1)

We use only a loop variable. No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force scans elements one by one, completely ignoring the fact that the array is sorted. In a sorted array, if we check the middle element and it's less than the target, we immediately know that the entire left half is also less than the target — there's no need to check any of them.

This is exactly the principle behind binary search: by checking the middle element, we can eliminate half of the remaining search space in each step. This reduces the time from O(n) to O(log n).

For an array of size 10^6:

  • Linear search: up to 1,000,000 comparisons.
  • Binary search: at most log₂(1,000,000) ≈ 20 comparisons.

That's a 50,000× speedup for large arrays.

Optimal Approach - Binary Search

Intuition

Since the array is sorted, we can use binary search to find the lower bound in O(log n) time.

The key observation is: the array can be divided into two logical regions:

  • Left region: All elements < target (these do NOT qualify as lower bound).
  • Right region: All elements >= target (these qualify, and we want the leftmost one).

We want to find the boundary between these two regions — the first index where the right region begins.

Binary search works by maintaining two pointers, low and high, and repeatedly checking the middle element:

  • If arr[mid] >= target: This could be the lower bound, but there might be an earlier one. Record mid as a candidate answer and search the left half (set high = mid - 1).
  • If arr[mid] < target: The lower bound must be to the right of mid. Search the right half (set low = mid + 1).

We initialize our result to n (the array length). This handles the edge case where all elements are smaller than the target — if no element qualifies, the result stays as n.

Step-by-Step Explanation

Let's trace through with arr = [2, 3, 7, 10, 11, 11, 25], target = 9:

Step 1: low = 0, high = 6, result = 7 (array length).

  • mid = (0 + 6) / 2 = 3. arr[3] = 10.
  • Is 10 >= 9? Yes! Record result = 3. Search left: high = 2.

Step 2: low = 0, high = 2.

  • mid = (0 + 2) / 2 = 1. arr[1] = 3.
  • Is 3 >= 9? No. Search right: low = 2.

Step 3: low = 2, high = 2.

  • mid = (2 + 2) / 2 = 2. arr[2] = 7.
  • Is 7 >= 9? No. Search right: low = 3.

Step 4: low = 3 > high = 2. Loop ends.

Result: result = 3. We found the lower bound in just 3 comparisons instead of 4!

Binary Search for Lower Bound — Watch how binary search halves the search space at each step. We track the best candidate answer and narrow down to the smallest valid index.

Algorithm

  1. Initialize low = 0, high = n - 1, and result = n.
  2. While low <= high:
    • Compute mid = low + (high - low) / 2 (to avoid integer overflow).
    • If arr[mid] >= target:
      • Update result = mid (this is a candidate lower bound).
      • Search the left half: high = mid - 1.
    • Else (arr[mid] < target):
      • Search the right half: low = mid + 1.
  3. Return result.

Why initialize result = n? If every element in the array is less than the target, the loop will never enter the arr[mid] >= target branch, and result will remain n — which is the correct lower bound by definition ("past the end of the array").

Code

#include <vector>
using namespace std;

class Solution {
public:
    int lowerBound(vector<int>& arr, int target) {
        int low = 0, high = arr.size() - 1;
        int result = arr.size();

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= target) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }
};
class Solution:
    def lowerBound(self, arr: list[int], target: int) -> int:
        low, high = 0, len(arr) - 1
        result = len(arr)

        while low <= high:
            mid = low + (high - low) // 2
            if arr[mid] >= target:
                result = mid
                high = mid - 1
            else:
                low = mid + 1

        return result
class Solution {
    public int lowerBound(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int result = arr.length;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= target) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each step of the while loop, we halve the search space. The loop runs at most ⌈log₂(n)⌉ times. For n = 10^6, this is at most 20 iterations — a massive improvement over the linear approach.

Space Complexity: O(1)

We use only three integer variables (low, high, result). No recursion is used, so there is no stack overhead.