Lesson 2 � Intermediate

Lower Bound, Upper Bound, Floor/Ceil

Basic binary search se thoda advance karte hain. Kabhi kabhi hume sirf exact match nahi, balki "pehla element jo x se bada ya barabar ho" ya "last occurrence" jaise variants chahiye. Ye sab binary search ke powerful extensions hain.

? 30 min✓ Intermediate✓ Binary Search basics

Bounds kya hote hain?

LOWER BOUND

Lower bound of x = pehla index jahan element >= x ho. MATLAB x ya usse bada pehla element kahan hai✓ Agar x hai array mein toh uska index, nahi hai toh jahan insert karna chahiye.

UPPER BOUND

Upper bound of x = pehla index jahan element > x ho. MATLAB x se strictly bada pehla element kahan hai✓ Agar x last element hai toh return len(arr).

FLOOR / CEIL

Floor(x) = array mein x se chhota ya barabar sabse bada element. Ceil(x) = array mein x se bada ya barabar sabse chhota element. Ye value return karte hain, index nahi.

# Sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# Target x = 15

Lower Bound(15) = 4 ✓ arr[4]=16 >= 15 (pehla index jahan >= 15)
Upper Bound(15) = 4 ✓ arr[4]=16 > 15 (pehla index jahan > 15)
Floor(15) = 12 ? 12 hai sabse bada jo <= 15
Ceil(15) = 16 ? 16 hai sabse chhota jo >= 15

# Target x = 23 (exact match hai)
Lower Bound(23) = 5 ✓ arr[5]=23 >= 23
Upper Bound(23) = 6 ✓ arr[6]=38 > 23
Floor(23) = 23
Ceil(23) = 23

Visual: Bounds on Sorted Array

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Index: 0 1 2 3 4 5 6 7 8 9

x = 15 ke liye:
Lower Bound: ?4 (16 � pehla jo >= 15)
Upper Bound: ?4 (16 � pehla jo > 15)
Floor: ?3 (12 � sabse bada jo <= 15)
Ceil: ?4 (16 � sabse chhota jo >= 15)

x = 23 ke liye:
Lower Bound: ?5 (23 � pehla jo >= 23)
Upper Bound: ?6 (38 � pehla jo > 23)
Floor: ?5 (23 � sabse bada jo <= 23)
Ceil: ?5 (23 � sabse chhota jo >= 23)

x = 100 ke liye:
Lower Bound: 10 (element nahi mila, end pe jaao)
Upper Bound: 10
Floor: ?9 (91 � sabse bada overall)
Ceil: None (bada element hai hi nahi)

Code Implementation

# Lower Bound: pehla index jahan arr[index] >= x
def lower_bound(arr, x):
 left, right = 0, len(arr)
 while left < right:
 mid = (left + right) // 2
 if arr[mid] < x:
 left = mid + 1
 else:
 right = mid
 return left

# Upper Bound: pehla index jahan arr[index] > x
def upper_bound(arr, x):
 left, right = 0, len(arr)
 while left < right:
 mid = (left + right) // 2
 if arr[mid] <= x:
 left = mid + 1
 else:
 right = mid
 return left

# Floor: x se chhota ya barabar sabse bada element
def floor(arr, x):
 idx = lower_bound(arr, x) - 1
 if idx >= 0:
 return arr[idx]
 return None

# Ceil: x se bada ya barabar sabse chhota element
def ceil(arr, x):
 idx = lower_bound(arr, x)
 if idx < len(arr):
 return arr[idx]
 return None

# Usage
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(arr, 15)) # 4
print(upper_bound(arr, 15)) # 4
print(floor(arr, 15)) # 12
print(ceil(arr, 15)) # 16

Key Difference: Lower bound mein if arr[mid] < x use hota hai (strictly less), upper bound mein if arr[mid] <= x (less or equal). Bas ek character ka difference hai � < vs <= � but result alag hota hai!

First & Last Occurrence

Ye lower/upper bound ka direct application hai:

# First occurrence of x = lower_bound(x)
# Last occurrence of x = upper_bound(x) - 1

def first_occurrence(arr, x):
 return lower_bound(arr, x)

def last_occurrence(arr, x):
 ub = upper_bound(arr, x)
 if ub > 0 and arr[ub - 1] == x:
 return ub - 1
 return -1

# Example
arr = [2, 5, 8, 12, 16, 23, 23, 23, 56, 91]
print(first_occurrence(arr, 23)) # 5
print(last_occurrence(arr, 23)) # 7
print(last_occurrence(arr, 100)) # -1

Try it: code khud likho

Exercise

Question: Sorted array [1, 2, 4, 4, 4, 7, 9] mein 4 ki pehli occurrence ka index kya hai✓ Answer mein index number daalo.

Question: Sorted array [2, 5, 8, 12, 16, 23] mein 10 ka floor (array mein 10 se chhota ya barabar sabse bada element) kya hai✓ Answer mein number daalo.

Common mistakes

Lower vs Upper bound confusion: Lower bound mein arr[mid] < x se left move karte hain (mid ko exclude), upper bound mein arr[mid] <= x se. Ek character ka difference hai but bahut important hai.
Return value: Lower/upper bound index return karte hain, floor/ceil value return karte hain. Question dhyan se padho � kya chahiye index ya value?
Empty result handle karna: Jab x array ke sabse chhota ya sabse bada ho, toh bounds array ke bahar ja sakte hain (index = len(arr)). Ye valid hai � check karo ki index in range hai ya nahi.
Sorted array assumption: Ye sab variants sirf sorted arrays pe kaam karte hain. Agar sorted nahi hai toh pehle sort karo (O(n log n)) ya linear approach use karo.

Lesson complete?

Bounds samajh aa gaye✓ Ab Rotated Sorted Array dekhte hain � binary search ka sabse interesting variant!