Binary SearchEasyO(log n) time · O(1) space

Upper Bound / Ceiling

Mahabharata — The Minimum Worthy — Finding the Least Warrior Not Below the Standard

न्यूनतमं यत् x-तुल्यं वा अधिकं — तत् सीमा। व्यवस्थिते सैन्ये — तं ज्ञातुं अर्धे विभज्य॥

*The minimum that equals or exceeds x — that is the ceiling. In the sorted army — find it by halving.*

The Story

Find the CEILING of x in a sorted array: the smallest element that is >= x.

For `arr = [1,3,4,7,8,10]`, x=5: ceiling is 7 (smallest ≥ 5). For `arr = [1,3,4,7,8,10]`, x=10: ceiling is 10 (exact match). For `arr = [1,3,4,7,8,10]`, x=11: no ceiling → return -1.

This is the `lower_bound` concept from C++ STL — the first position where a value ≥ x exists.

**Binary search for ceiling:** Key modification from bs-1: we're NOT looking for an exact match. We're looking for the FIRST element >= x.

```java int left=0, right=n-1, result=-1; while (left <= right) { int mid = left + (right-left)/2; if (arr[mid] >= x) { result = mid; // This could be the ceiling — save it right = mid-1; // Look for smaller (earlier) candidate in left half } else { left = mid+1; // arr[mid] too small, look right } } return result; // -1 if no element >= x ```

Trace `[1,3,4,7,8,10]`, x=5: - l=0,r=5,mid=2,arr[2]=4 < 5 → left=3 - l=3,r=5,mid=4,arr[4]=8 >= 5 → result=4, right=3 - l=3,r=3,mid=3,arr[3]=7 >= 5 → result=3, right=2 - l=3>r=2 → stop. Return result=3 (index of 7) ✓

"We save the index whenever we find a candidate (>= x) and then search LEFT for a smaller candidate," Arjuna learned. "The last saved index is the ceiling's index."

This "save and search the other half" pattern appears in bs-3 (first/last position) and many other binary search variants.

The Linear Ceiling Finder

Scan from left. Return first element >= x. O(n).

java

int findCeilBruteForce(long[] arr, int n, long x) {
    for (int i = 0; i < n; i++)
        if (arr[i] >= x) return i;
    return -1;
}

The Save-and-Search-Left Wisdom

When arr[mid] >= x: save result=mid, search left half for smaller candidate (right=mid-1). When arr[mid] < x: search right (left=mid+1). Return saved result.

java

int findCeil(long[] arr, int n, long x) {
    int left = 0, right = n - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            result = mid;   // Potential ceiling
            right = mid - 1; // Look for smaller candidate
        } else {
            left = mid + 1;  // Too small, search right
        }
    }
    return result;  // Index of ceiling, -1 if none
}

Step-by-Step Walkthrough

[1,3,5], x=3
l=0,r=2,mid=1,arr[1]=3>=3 → res=1,r=0
l=0,r=0,mid=0,arr[0]=1<3 → l=1
l=1>r=0. Return 1 (value=3, exact match) ✅

Deep Insight

**Floor vs Ceiling:** - Floor (largest element <= x): when arr[mid]<=x: save result, search RIGHT; when >x: search left - Ceiling (smallest element >= x): when arr[mid]>=x: save result, search LEFT; when <x: search right

**The 'save and continue' pattern:** Instead of returning immediately when finding a satisfying mid, we SAVE the result and continue searching for a better (smaller/larger) candidate in the appropriate half. This single modification to bs-1 enables finding first/last occurrence, floor, ceiling, etc.

**bs-3 extends this** to find first AND last occurrence using two separate binary searches with this same save-and-continue pattern.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Linear scan
Optimal	O(log n)	O(1)	Binary search with save-and-continue

Pattern Recognition

✅ Ceiling = smallest element >= x
✅ When arr[mid]>=x: save result, search LEFT (right=mid-1)
✅ When arr[mid]<x: search RIGHT (left=mid+1)
✅ Return saved result (-1 if none)

**LeetCode Trigger Phrases:**
→ "upper bound" / "ceiling" in sorted array
→ "first element >= x" (lower_bound)
→ "smallest element not less than x"

Bhagavad Gita 6.5

उद्धरेदात्मनात्मानं नात्मानमवसादयेत्। आत्मैव ह्यात्मनो बन्धुरात्मैव रिपुरात्मनः॥

Let a person uplift the self by the self; let them not degrade the self. For the self alone is the friend of the self, and the self alone is the enemy of the self.

Connection: The ceiling search seeks the minimum threshold — the lowest bar one must clear to be 'above x'. Like the Gita's call for self-elevation, the algorithm searches for the least element that rises to meet the standard. It saves every qualifying candidate while continuing to search for a better (more minimal) one. This disciplined persistence — saving progress while still seeking improvement — embodies the yogi's path of constant self-refinement.