Find Lower Bound in Sorted Array

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

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.

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

int lowerBound(vector<int>& arr, int x) {
  int low = 0, high = arr.size() - 1, ans = arr.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() {
  vector<int> arr = {1, 2, 4, 4, 5, 6};
  int x = 4;
  cout << "Lower Bound Index: " << lowerBound(arr, x) << endl;
  return 0;
}

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

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

  public static void main(String[] args) {
    int[] arr = {1, 2, 4, 4, 5, 6};
    int x = 4;
    System.out.println("Lower Bound Index: " + lowerBound(arr, x));
  }
}

function lowerBound(arr, x) {
  let low = 0, high = arr.length - 1;
  let ans = arr.length;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] >= x) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

// Sample Input
const arr = [1, 2, 4, 4, 5, 6];
const x = 4;
console.log("Lower Bound Index:", lowerBound(arr, x));

package main

import (
  "fmt"
)

func lowerBound(arr []int, x int) int {
  low, high := 0, len(arr)-1
  ans := len(arr)
  for low <= high {
    mid := (low + high) / 2
    if arr[mid] >= x {
      ans = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return ans
}

func main() {
  arr := []int{1, 2, 4, 4, 5, 6}
  x := 4
  fmt.Println("Lower Bound Index:", lowerBound(arr, x))
}

fn lower_bound(arr: &Vec<i32>, x: i32) -> usize {
    let (mut low, mut high) = (0, arr.len() as i32 - 1);
    let mut ans = arr.len();
    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid as usize] >= x {
            ans = mid as usize;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    ans
}

fn main() {
    let arr = vec![1, 2, 4, 4, 5, 6];
    let x = 4;
    println!("Lower Bound Index: {}", lower_bound(&arr, x));
}

fun lowerBound(arr: IntArray, x: Int): Int {
    var low = 0
    var high = arr.size - 1
    var ans = arr.size
    while (low <= high) {
        val mid = (low + high) / 2
        if (arr[mid] >= x) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 4, 5, 6)
    val x = 4
    println("Lower Bound Index: ${lowerBound(arr, x)}")
}

func lowerBound(_ arr: [Int], _ x: Int) -> Int {
    var low = 0
    var high = arr.count - 1
    var ans = arr.count
    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] >= x {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

let arr = [1, 2, 4, 4, 5, 6]
let x = 4
print("Lower Bound Index: \(lowerBound(arr, x))")

function lowerBound(arr: number[], x: number): number {
  let low = 0, high = arr.length - 1;
  let ans = arr.length;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] >= x) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

const arr: number[] = [1, 2, 4, 4, 5, 6];
const x = 4;
console.log("Lower Bound Index:", lowerBound(arr, x));

Time complexity

Space complexity

O(1)

The algorithm operates in-place and uses a fixed number of variables (like low, high, mid, and ans), resulting in constant extra space usage.