Binary Search: Lower Bound, Upper Bound, Search Insert Position, Floor & Ceil

Binary search is not merely a mechanism for finding an exact value in a sorted collection; it is a foundational framework for searching across non-decreasing search spaces. By tweaking the conditional check during middle-element evaluations, binary search expands into solving fundamental boundary problems such as finding the lower bound, upper bound, optimal insertion points, and range limits (floor and ceiling).

1. Fundamentals of Lower Bound

Core Definition

The Lower Bound of a target value $X$ in a sorted array is defined as the smallest index idx such that the element at that index is greater than or equal to $X$:

If no element in the array satisfies $\text{arr}[\text{idx}] \ge X$, the lower bound defaults to the hypothetical index beyond the last element, which is $N$ (where $N$ is the size of the array).

Note: For lower bound to function correctly, the array must be sorted in non-decreasing order.

Real-Life Analogy

Imagine walking down a row of mailboxes labeled with house numbers in ascending order ([1, 2, 3, 7, 8, 9, 15]). If you are tasked with delivering a package to address #6 or the next immediate house if #6 does not exist, you walk until you see the first house whose number is $\ge 6$. In this case, house #7 is the lower bound.

Naive Approach vs. Binary Search

• Naive Approach (Linear Search): Iterate from index 0 to N - 1. Stop at the first index where $\text{arr}[\text{idx}] \ge X$.
  • Time Complexity: $O(N)$
  • Space Complexity: $O(1)$
• Optimal Approach (Binary Search): Utilize the sorted property to divide the search space in half at each iteration.
  • Time Complexity: $O(\log_2 N)$
  • Space Complexity: $O(1)$

2. Binary Search Implementation of Lower Bound

The "Probable Answer" Strategy (ans Variable Technique)

When performing binary search for boundaries, maintain an ans variable initialized to $N$ (the default fallback if no valid index is found).

1. Calculate mid = low + (high - low) / 2.
2. Check if arr[mid] >= X:
   • If true, mid is a potential lower bound candidate. Store ans = mid.
   • Because we want the smallest index, eliminate the right search space by moving left: high = mid - 1.
3. If false (arr[mid] < X):
   • mid cannot be an answer, nor can any index to its left. Eliminate the left search space by moving right: low = mid + 1.

Search Space Reduction Workflow

Step-by-Step Execution Trace

Consider arr = [1, 2, 3, 3, 7, 8, 9, 9, 9, 15] ($N = 10$) and $X = 1$:

C++ / Java / Python Source Code

Custom Implementation (C++)

#include <vector>
#include <iostream>

int lowerBound(const std::vector<int>& arr, int n, int x) {
    int low = 0;
    int high = n - 1;
    int ans = n; // Default hypothetical index if no element >= x exists

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] >= x) {
            ans = mid;        // Store probable answer
            high = mid - 1;   // Search left space for a smaller index
        } else {
            low = mid + 1;    // Search right space
        }
    }
    return ans;
}

C++ STL Built-In Utility

In C++, std::lower_bound returns an iterator to the first element that is $\ge X$. Subtracting the base iterator gives the index:

#include <algorithm>
#include <vector>

// For vectors
int idx = std::lower_bound(arr.begin(), arr.end(), x) - arr.begin();

// For sub-ranges [index 2 to 6]
int subIdx = std::lower_bound(arr.begin() + 2, arr.begin() + 7, x) - arr.begin();

3. Fundamentals of Upper Bound

Core Definition

The Upper Bound of a target value $X$ in a sorted array is defined as the smallest index idx such that the element at that index is strictly greater than $X$:

If no element is strictly greater than $X$, the upper bound defaults to $N$.

Lower Bound vs. Upper Bound Comparison

4. Binary Search Implementation of Upper Bound

Algorithm & Code Logic

The algorithm for Upper Bound matches Lower Bound, with one strict condition change: replacing >= with >.

#include <vector>

int upperBound(const std::vector<int>& arr, int n, int x) {
    int low = 0;
    int high = n - 1;
    int ans = n;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] > x) {
            ans = mid;        // Candidate upper bound found
            high = mid - 1;   // Search left for a smaller index
        } else {
            low = mid + 1;    // Value <= x, search right
        }
    }
    return ans;
}

C++ STL Utility

int idx = std::upper_bound(arr.begin(), arr.end(), x) - arr.begin();

5. Application 1: Search Insert Position

Problem Context

Given a sorted array of distinct integers and a target $X$, return the index if $X$ is found. If not found, return the index where $X$ would be inserted to maintain sorted order.

Conceptual Reduction to Lower Bound

Consider inserting $X = 6$ into arr = [1, 2, 4, 7]:

• To preserve sorted order, $6$ must sit before $7$. The index of $7$ is 3.
• If $X = 2$ (which exists in arr), it should be placed at index 1.

In both cases, we are seeking the smallest index where $\text{arr}[\text{idx}] \ge X$.

Key Insight: Search Insert Position is identical to the Lower Bound problem.

int searchInsert(std::vector<int>& arr, int m) {
    int n = arr.size();
    int low = 0, high = n - 1;
    int ans = n;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] >= m) {
            ans = mid;
            high = mid - 1; // Look left
        } else {
            low = mid + 1;  // Look right
        }
    }
    return ans;
}

6. Application 2: Floor and Ceil in a Sorted Array

Definitions

Given a sorted array and a value $X$:

1. Floor: The largest element in the array that is less than or equal to $X$ ($\le X$).
2. Ceiling: The smallest element in the array that is greater than or equal to $X$ ($\ge X$).

Deriving Floor and Ceil via Binary Search

• Ceil: Directly maps to the value at the Lower Bound index.
• Floor: Requires reversing the binary search logic:
  • Condition: arr[mid] <= X
  • If true, arr[mid] is a candidate floor. Record ans = arr[mid]. Because we want the largest value, move right (low = mid + 1) to find a bigger valid number.
  • If false (arr[mid] > X), move left (high = mid - 1).

#include <vector>
#include <utility>

int findFloor(const std::vector<int>& arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1; // Default if no element <= x exists

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] <= x) {
            ans = arr[mid];  // Probable floor value
            low = mid + 1;   // Search right for a larger candidate <= x
        } else {
            high = mid - 1;  // Search left
        }
    }
    return ans;
}

int findCeil(const std::vector<int>& arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1; // Default if no element >= x exists

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] >= x) {
            ans = arr[mid];  // Probable ceil value
            high = mid - 1;  // Search left for a smaller candidate >= x
        } else {
            low = mid + 1;   // Search right
        }
    }
    return ans;
}

std::pair<int, int> getFloorAndCeil(std::vector<int>& arr, int n, int x) {
    int f = findFloor(arr, n, x);
    int c = findCeil(arr, n, x);
    return {f, c};
}

7. Comparative Synthesis & Key Patterns

The following matrix synthesizes the structural patterns for variants of Binary Search on sorted arrays:

Optimization Insight: In standard lower/upper bound loops, upon loop termination (low > high), the low pointer automatically converges to the optimal lower bound index, while high converges to the floor index. Utilizing an explicit ans variable, however, prevents off-by-one errors and reduces mental overhead during implementation.

Summary and Key Takeaways

• Lower Bound Concept: Finds the first index idx where $\text{arr}[\text{idx}] \ge X$. If no such element exists, returns array size $N$.
• Upper Bound Concept: Finds the first index idx where $\text{arr}[\text{idx}] > X$. Crucial for range-query operations.
• Search Space Truncation: Binary search eliminates half of the remaining elements per step by determining whether a candidate answer exists in the left or right sub-array.
• Identical Reductions: Problems like Search Insert Position and Ceiling of an Element are direct re-applications of Lower Bound.
• Floor Inversion: Computing the Floor flips the search direction—when arr[mid] <= X, record the value and push low rightward to maximize the valid floor candidate.
• Time Complexity: All variants run in optimal $O(\log_2 N)$ logarithmic time complexity and require $O(1)$ auxiliary space.