Lower Bound in Sorted Array Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int lowerBound(int arr[], int size, int x) {
  int low = 0, high = size - 1, ans = size;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] >= x) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

int main() {
  int arr[] = {1, 2, 4, 4, 5, 6};
  int size = sizeof(arr) / sizeof(arr[0]);
  int x = 4;
  printf("Lower Bound Index: %d\n", lowerBound(arr, size, x));
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The lower bound is found at the very first mid index comparison in the binary search.
Average CaseO(log n)With each iteration, the binary search reduces the search space by half to locate the correct lower bound.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...