DSA sheet · Binary Search · Lower & upper bound pattern

Floor & Ceiling in a Sorted Array

Two problems taught together because they are mirror images of each other. The floor of x is the biggest value that is still ≤ x. The ceiling is the smallest value that is still ≥ x. The teacher solves floor carefully, then shows that ceiling needs only the comparison and the two pointer moves swapped. Both use the trick from First & Last Position: when mid could be the answer, save it in ans and keep searching for a better one.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (incl. lower vs upper bound)
• Part A · Floor: brute force (linear scan)
• Part B · Floor: binary search
• Part C · Ceiling: binary search
• Part D · Floor & ceiling as upper / lower bound
• Part E · Revision page

Part 0 · Before starting

Why binary search works here

The array is sorted. For floor with x = 5, ask each cell "is arr[i] <= 5?" In [1, 2, 8, 10, 11, 12, 19] the answers are yes yes no no no no no. In a sorted array these answers switch only once, and the floor is the last "yes". Binary search finds a switch point by checking the middle and discarding the half that can't contain it.

left, right, mid

• left (low) starts at index 0, right (high) at the last index, len(arr) - 1. The search area is everything from left to right, both included.
• mid is the middle index of that area. Based on arr[mid] we decide: go left, go right, or note it as an answer.
• "Going left" = right = mid - 1. "Going right" = left = mid + 1. Nothing is deleted from the array.
• while left <= right: the area is empty only when the pointers cross.

Why mid = left + (right - left) // 2?

There are two ways to compute mid: (left + right) // 2, or left + (right - left) // 2. They give the same value. In Java/C++, if the range is very big, left + right can exceed the largest int and overflow (wrap to a wrong, negative number). The second form never builds a number bigger than right. The teacher's advice: always use the second form, so you never have to worry about it. Python integers can't overflow, so in Python it's only a habit, but a good one.

Lower bound vs upper bound, and where floor and ceiling land

• Lower bound of x = first index with value ≥ x. That is the ceiling (and if x repeats, it's the first copy).
• Upper bound of x = first index with value > x. One step to its left is the last value ≤ x, which is the floor (and if x repeats, it's the last copy).

arr = [1, 2, 8, 10, 10, 12, 19], x = 5 (not in the array):

Same array, x = 10 (present twice):

  x = 5:   1   2 | 8   10  10  12  19        x = 10:  1   2   8 [10  10] 12  19
               ^   ^                                           ^    ^   ^
           floor   ceil (LB = UB = 2)                       ceil floor  UB
           = UB-1                                           = LB = UB-1

Part A · Floor: brute force (linear scan)

GeeksforGeeks · Floor in a Sorted Array

1The question in simple words

You get a sorted array arr and a number x. Find the largest element that is ≤ x (the floor of x) and return its index (0-based). Two extra rules:

• If no element is ≤ x, return −1.
• If the floor value appears several times, return the index of its last occurrence.

2What the constraints tell us

• Array size up to 10⁶, and at least 1 element.
• Values from 1 to 10⁶: no negative numbers, all small enough for a normal int.
• 10⁶ steps is well below the ~10⁸ that gives TLE, so a linear scan will pass. But the array is sorted, and the teacher repeats her rule: any extra information in a question has a use. Sorted → binary search.

3Intuition

Walk from left to right. As long as the value is ≤ x, it's a candidate, and since values only grow, each new candidate is better than the last one. So keep overwriting ans. The moment you see a value bigger than x, nothing later can be ≤ x, so stop.

4Building it from example 1 (x = 5)

• 1 ≤ 5 → candidate, ans = 0. (We store indexes, not values, because the question wants an index.)
• 2 ≤ 5 → better candidate, ans = 1.
• 8 > 5 → stop. Answer 1.

Duplicates are handled for free: on […, 10, 10, 12] with x = 11, the second 10 overwrites the first, so we end on the last occurrence, as required.

5Approach steps

1. ans = -1.
2. For each index i: if arr[i] <= x → ans = i, otherwise break.
3. Return ans.

6Code (Python)

class Solution:
    def findFloor(self, arr, x):
        ans = -1
        for i in range(len(arr)):
            if arr[i] <= x:
                ans = i          # a bigger (or equal, later) candidate
            else:
                break            # sorted: everything after is > x too
        return ans

7Code line by line

8Dry run (x = 5)

9Complexity & remember

Time O(n) in the worst case (x bigger than everything). Space O(1).

Part B · Floor: binary search

1The question

Same as Part A: index of the largest value ≤ x (last copy if repeated), or −1. Now in O(log n).

2Constraints

n ≤ 10⁶ → about 20 binary-search steps. The array is never empty, so right = n - 1 is a valid index.

3Intuition

When mid's value is too big (> x), it's useless, and so is everything to its right. When mid's value is ≤ x, it's a possible floor. Save it, but a bigger value that is still ≤ x might exist further right, so keep looking there. It's the same "save, then keep going" idea from First & Last Position.

4Building the conditions from examples

Example 1: arr = [1, 2, 8, 10, 11, 12, 19], x = 5. left = 0, right = 6 → mid = 0 + (6 − 0) // 2 = 3.

Case 1: arr[mid] > x → go left, right = mid - 1

10 is bigger than 5. A floor must be ≤ 5, so 10 can't be it, and neither can anything to its right (all ≥ 10). Search the left part. Why mid - 1 and not mid? Because we just saw that mid is too big. It can never be the answer, so there's no reason to keep it.

Case 2: arr[mid] < x → save it, go right

New mid = 0 + (2 − 0) // 2 = 1 → value 2. 2 < 5, so 2 could be the floor. But maybe there's something bigger than 2 that's still ≤ 5 on its right. Since the array is sorted, bigger values are only on the right. So:

• save it: ans = mid (the index, because the question returns an index),
• search right: left = mid + 1.

We start with ans = -1: if no value ≤ x is ever seen, −1 is returned, as the question wants.

Case 3: arr[mid] == x → what then? (her thought experiment)

The teacher asks: what if x were 10 instead of 5 (on example 2's array [1, 2, 8, 10, 10, 12, 19])? The first mid (index 3) is 10, an exact match. Can we return 3 right away? No. The question says that for repeats we must return the last occurrence, and there's another 10 at index 4. Just like in First & Last Position, a later copy can only be on the right. So we save mid and go right.

Then she notices that this is exactly what we already do for "less than": save, then left = mid + 1. So the two cases merge into one condition with <=:

5Approach steps

1. left = 0, right = len(arr) - 1, ans = -1.
2. While left <= right: mid = left + (right - left) // 2.
3. If arr[mid] <= x: ans = mid, left = mid + 1 (look for a bigger floor on the right).
4. Else: right = mid - 1 (too big, look left).
5. Return ans.

6Code (Python)

class Solution:
    def findFloor(self, arr, x):
        left, right = 0, len(arr) - 1      # last INDEX, not len(arr)
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] <= x:
                ans = mid                  # a possible floor: save it
                left = mid + 1             # try for a bigger one on the right
            else:
                right = mid - 1            # too big: go left
        return ans

7Code line by line

8Dry runs (hand tables)

Example 1: [1, 2, 8, 10, 11, 12, 19], x = 5

Example 2 (duplicates): [1, 2, 8, 10, 10, 12, 19], x = 11

Her x = 10 thought experiment on the same array follows the exact same steps (10 ≤ 10 at index 3, 12 > 10, 10 ≤ 10 at index 4) → 4. And with x = 0: mids 3 → 1 → 0 are all too big, and ans stays −1.

9Complexity & remember

• Time O(log₂ n): every step discards half of what's left.
• Space O(1).

Part C · Ceiling: binary search

GeeksforGeeks · Ceil in a Sorted Array

1The question in simple words

Same input. Now find the smallest element that is ≥ x (the ceiling of x) and return its index. If none exists, return −1. If the ceiling value appears several times, return the first occurrence (floor asked for the last one).

2Constraints

Same as floor: up to 10⁶ elements, values 1..10⁶. A linear scan would pass (stop at the first value ≥ x), but the sorted array calls for binary search.

3Intuition: floor, flipped

For the ceiling, a value ≥ x is a possible answer, but a smaller one that's still ≥ x might be on the left. So: save it, go left. A value < x is useless, together with everything left of it, so go right. Every arrow from the floor version is reversed.

4Building the conditions from example 1 (x = 5)

• mid = 3 → 10. 10 ≥ 5, so it could be the ceiling. Save ans = 3. Something smaller but still ≥ 5 could exist on the left, so right = mid - 1 = 2.
• mid = 1 → 2. 2 < 5. Do we want it? No, because the ceiling must be ≥ 5. Everything left of it is even smaller, so go right: left = mid + 1 = 2.
• mid = 2 → 8. 8 ≥ 5 → save ans = 2, right = 1. The pointers cross → return 2 ✓.

The equal case is folded in again (that's the = in >=). On an exact match, we save it and keep going left, so with duplicates we end on the first copy, which is what the question asks for. Example 3 shows it: with x = 0 we save 3 (value 8), then 1 (value 1), then 0 (value 1) → answer 0.

5Approach steps

1. left = 0, right = len(arr) - 1, ans = -1.
2. While left <= right: compute mid.
3. If arr[mid] >= x: ans = mid, right = mid - 1 (look for a smaller ceiling on the left).
4. Else: left = mid + 1.
5. Return ans.

6Code (Python)

class Solution:
    def findCeil(self, arr, x):
        left, right = 0, len(arr) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] >= x:
                ans = mid                  # a possible ceiling: save it
                right = mid - 1            # try for a smaller one on the left
            else:
                left = mid + 1             # too small: go right
        return ans

7Code line by line

8Dry run (hand table)

Example 1: [1, 2, 8, 10, 11, 12, 19], x = 5

Example 3 (duplicates): [1, 1, 2, 8, 10, 11, 12, 19], x = 0

With x = 20, every mid is too small, left runs past the end, and ans stays −1.

9Complexity & remember

O(log n) time, O(1) space.

Part D · Floor & ceiling as upper / lower bound

Not shown in the video. This is added to connect these problems to the pattern's name.

1The connection

Look at what each search really finds:

• Ceiling = the first index with value ≥ x = the lower bound of x.
• Floor = the last index with value ≤ x = (first index with value > x) − 1 = upper bound − 1.

Floor and ceiling meet on the same index exactly when x is in the array once. When x is missing, the floor is right before the ceiling (floor = ceil − 1).

2Code (Python)

def lower_bound(arr, x):          # first index with arr[i] >= x  (n if none)
    left, right, ans = 0, len(arr) - 1, len(arr)
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= x:
            ans, right = mid, mid - 1
        else:
            left = mid + 1
    return ans

def upper_bound(arr, x):          # first index with arr[i] > x   (n if none)
    left, right, ans = 0, len(arr) - 1, len(arr)
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] > x:
            ans, right = mid, mid - 1
        else:
            left = mid + 1
    return ans

def find_ceil(arr, x):
    lb = lower_bound(arr, x)
    return lb if lb < len(arr) else -1     # n means "nothing is >= x"

def find_floor(arr, x):
    return upper_bound(arr, x) - 1           # 0 - 1 = -1 means "nothing is <= x"

Notice that lower_bound here is the ceiling code with ans starting at n instead of −1, and in Python bisect.bisect_left / bisect.bisect_right are these same two bounds.

3Complexity

One binary search each: O(log n) time, O(1) space.

Part E · Revision page

s = Solution()
print(s.findFloor([1, 2, 8, 10, 11, 12, 19], 5))      # 1
print(s.findFloor([1, 2, 8, 10, 10, 12, 19], 11))     # 4
print(s.findFloor([1, 2, 8, 10, 10, 12, 19], 0))      # -1
print(s.findCeil([1, 2, 8, 10, 11, 12, 19], 5))       # 2
print(s.findCeil([1, 2, 8, 10, 11, 12, 19], 20))      # -1
print(s.findCeil([1, 1, 2, 8, 10, 11, 12, 19], 0))    # 0

Based on this video: Floor in a Sorted Array & Ceil in a Sorted Array