Loading…

easyBinary SearchFrequently asked

Floor and Ceil in a Sorted Array

Q: How do you solve Floor and Ceil in a Sorted Array using the Linear Scan approach?

When to use it: Open with this — it makes the definitions concrete and sets up why the sorted order lets us do better. The definition-driven baseline simply checks every element. **The literal method.** Iterate once. Each element ≤ x updates the floor candidate (since the array is non-decreasing, the last such element is the true floor). The first element ≥ x is the ceil. Keep both as you go. **Why it's correct but slow.** It never uses the sorted structure beyond a possible early exit. For a single small array it's perfectly fine and is the clearest way to state what floor and ceil mean. But with `n` up to 10⁶ or many queries against the same array, paying `O(n)` per query is exactly what binary search removes. Time complexity: O(n). Space complexity: O(1).

Binary Search · 14 of 16 · 9 min

Given a sorted (non-decreasing) array arr and a value x, return the floor of x (the largest element ≤ x) and the ceil of x (the smallest element ≥ x).

If no floor exists (every element is greater than x), return a sentinel such as −1 for the floor. Likewise return −1 for the ceil if no element is ≥ x.

In plain English

On a sorted array you want the nearest element that doesn't overshoot (floor) and the nearest that doesn't undershoot (ceil) relative to x. Because the array is ordered, the set of elements ≤ x forms a prefix and the set ≥ x forms a suffix, so each boundary can be found by binary search instead of a scan — keep the best candidate as you converge.

Examples

Example 1

Input: arr = [1, 2, 8, 10, 12, 19], x = 5
Output: floor = 2, ceil = 8
Note: Largest element ≤ 5 is 2; smallest element ≥ 5 is 8.

Example 2

Input: arr = [1, 2, 8, 10, 12, 19], x = 10
Output: floor = 10, ceil = 10
Note: x is present, so both floor and ceil are 10.

Example 3

Input: arr = [5, 7, 9], x = 3
Output: floor = -1, ceil = 5
Note: No element ≤ 3 → floor sentinel; smallest ≥ 3 is 5.

Constraints

0 ≤ n ≤ 10⁶, arr sorted in non-decreasing order
Values fit in a 32-bit integer (use long for mid only if indices are huge — here indices fit)
Array may contain duplicates
Return a sentinel (−1) when floor or ceil does not exist

Clarifying questions4First question: What should I return when floor or ceil doesn't exist?Explore questions

Q1.What should I return when floor or ceil doesn't exist?
A sentinel like −1 (or report 'none'). Confirm, because returning the wrong sentinel is a common silent bug.
Q2.Can the array contain duplicates?
Yes. With duplicates equal to x, floor and ceil both equal x; the ≤/≥ comparisons handle it without special cases.
Q3.Is the array guaranteed sorted?
Binary search requires it. If not sorted, you'd sort first (O(n log n)) or scan linearly.
Q4.Do you want the values or their indices?
Either is easy — record the candidate index instead of the value if positions are needed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

In a sorted array, the floor of x is the largest element ≤ x and the ceil is the smallest element ≥ x. A linear scan is O(n); binary search makes both O(log n). Floor: move right whenever arr[mid] ≤ x (recording mid as a candidate), else move left. Ceil is the mirror: move left whenever arr[mid] ≥ x (recording the candidate), else move right. If no element qualifies, return a sentinel like −1.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can adapt plain binary search from 'find an exact match' to 'find the closest element on a given side', tracking a candidate instead of returning immediately.

Where candidates slip

Returning -1 when x isn't present (treating it like exact search), mixing up which half to keep for floor vs ceil, or off-by-one with mid ± 1.

How to stand out

Present floor and ceil as mirror searches, handle the not-found sentinel cleanly, and connect them to lower_bound / upper_bound and insertion position.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(n)`	`O(1)`	Open with this — it makes the definitions concrete and sets up why the sorted order lets us do better.	Read
2	Binary Search for the Boundary (Optimal)Optimal	`O(log n)`	`O(1)`	The intended answer. Stress that you record a candidate and keep searching the better side instead of returning on an exact hit.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewarr[mid] vs xComputing FLOOR?YesNo (CEIL)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(n)SpaceO(1)

Open with this — it makes the definitions concrete and sets up why the sorted order lets us do better.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk the array once. Track the largest value seen that is ≤ x (floor) and, separately, the smallest value that is ≥ x (ceil).

2Hint 2Explore hint

Because the array is sorted you could stop early, but a plain scan ignores that and checks everything.

3Hint 3Explore hint

n comparisons per query — fine for small n, wasteful when n is large or there are many queries.

A · Core idea

The definition-driven baseline simply checks every element.

The literal method. Iterate once. Each element ≤ x updates the floor candidate (since the array is non-decreasing, the last such element is the true floor). The first element ≥ x is the ceil. Keep both as you go.

Why it's correct but slow. It never uses the sorted structure beyond a possible early exit. For a single small array it's perfectly fine and is the clearest way to state what floor and ceil mean. But with n up to 10⁶ or many queries against the same array, paying O(n) per query is exactly what binary search removes.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 8, 10, 12, 19], x = 5

Array state

at 2

2 ≤ 5 → floor = 2

[0]

i ↓

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultfloor = 2, ceil = 8

C · Code with teaching comments

Reference implementation previewpublic class LinearFloorCeil { public int[] floorCeil(int[] arr, int x) { int floor = -1, ceil = -1; for (int v : arr) { if (v <= x) floor = v;Explore the full code

solution.javaJava

Linear Scan — reference

2 teaching notes

1
public class LinearFloorCeil {
2
    public int[] floorCeil(int[] arr, int x) {
3
        int floor = -1, ceil = -1;
4
        for (int v : arr) {
5
            // Sorted order means the last element ≤ x is the floor.
6
            if (v <= x) floor = v;
7
            // The first element ≥ x is the ceil; lock it once.
8
            if (v >= x && ceil == -1) ceil = v;
9
        }
10
        return new int[]{floor, ceil};
11
    }
12
 
13
    public static void main(String[] args) {
14
        int[] r = new LinearFloorCeil().floorCeil(new int[]{1, 2, 8, 10, 12, 19}, 5);
15
        System.out.println(r[0] + " " + r[1]);
16
    }
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The scan's cost comes from ignoring order. Sorted data means 'elements ≤ x' is a contiguous prefix — so the floor is just the last index of that prefix, which binary search finds in O(log n).

ComplexityO(n) time, O(1) space — One pass over n elements with O(1) work each → O(n). Constant extra space for the two candidates.

E · Edge cases and pitfalls3Forgetting the sentinel when no floor/ceil exists.Explore edge cases

Pitfalls

Forgetting the sentinel when no floor/ceil exists.
Overwriting ceil on every match instead of only the first.
Treating O(n) as fine for huge arrays or many repeated queries.

03.2

Approach 2 of 2 · Optimal

Binary Search for the Boundary (Optimal)

TimeO(log n)SpaceO(1)

The intended answer. Stress that you record a candidate and keep searching the better side instead of returning on an exact hit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The elements ≤ x form a prefix of the sorted array; the floor is the last element of that prefix. Binary-search for that boundary.

2Hint 2Explore hint

When arr[mid] ≤ x, mid is a valid floor candidate — record it and search right (lo = mid + 1) for a possibly larger valid value. Otherwise search left.

3Hint 3Explore hint

Ceil mirrors it: when arr[mid] ≥ x, record it and search left (hi = mid − 1) for a smaller valid value; otherwise search right.

A · Core idea

Both floor and ceil are the same binary search with mirrored comparisons; the key change from textbook binary search is that you don't stop on an exact match — you stash a candidate and keep going toward the best one.

Floor — largest element ≤ x. The values ≤ x occupy a prefix of the array, and the floor is that prefix's last element. Run binary search: at mid, if arr[mid] <= x, then mid qualifies, so record arr[mid] as the current best and move right (lo = mid + 1) to look for an even larger value that still doesn't exceed x. If arr[mid] > x, this position overshoots, so move left (hi = mid − 1). When the loop ends, the last recorded candidate is the floor; if nothing was ever recorded, return −1.

Ceil — smallest element ≥ x. Mirror everything. The values ≥ x form a suffix, and the ceil is its first element. At mid, if arr[mid] >= x, record it and move left (hi = mid − 1) seeking a smaller value still at least x. If arr[mid] < x, move right (lo = mid + 1). The last recorded candidate is the ceil.

Why equality needs no special case. If x is present, the <= in floor and the >= in ceil both treat the equal element as a valid candidate, so floor and ceil naturally collapse to x. You don't branch on 'found exactly'.

Overflow-safe mid. Compute mid = lo + (hi − lo) / 2 rather than (lo + hi) / 2; for large indices the latter can overflow. It also keeps the off-by-one reasoning clean: the mid ± 1 updates guarantee the window strictly shrinks, so the loop always terminates.

Relation to lower_bound / upper_bound. Ceil is exactly lower_bound(x) (first element ≥ x); the element just before upper_bound(x) is the floor. Recognising floor/ceil as these standard boundaries lets you reuse one mental template for insertion position, nearest element, and range counting.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 8, 10, 12, 19], x = 5 — compute FLOOR

Array state

mid=2

8 > 5 → discard right half, hi=1

[0]

[1]

mid ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultfloor = 2 (ceil by mirror = 8)

C · Code with teaching comments

solution.javaJava

Binary Search for the Boundary (Optimal) — optimal

5 teaching notes

1
public class BinaryFloorCeil {
2
    public int floor(int[] arr, int x) {
3
        int lo = 0, hi = arr.length - 1, ans = -1;
4
        while (lo <= hi) {
5
            // Overflow-safe midpoint; never compute (lo+hi)/2 for large indices.
6
            int mid = lo + (hi - lo) / 2;
7
            // Floor: arr[mid] qualifies — it's ≤ x.
8
            if (arr[mid] <= x) {
9
                // Stash the candidate and keep searching the right half for something
10
                // closer to x.
11
                ans = arr[mid];   // candidate, then try for a larger valid value
12
                lo = mid + 1;
13
            } else {
14
                // Search left for a smaller value still ≥ x.
15
                hi = mid - 1;
16
            }
17
        }
18
        return ans;
19
    }
20
 
21
    public int ceil(int[] arr, int x) {
22
        int lo = 0, hi = arr.length - 1, ans = -1;
23
        while (lo <= hi) {
24
            int mid = lo + (hi - lo) / 2;
25
            // Ceil mirror: arr[mid] qualifies — it's ≥ x.
26
            if (arr[mid] >= x) {
27
                ans = arr[mid];   // candidate, then try for a smaller valid value
28
                hi = mid - 1;
29
            } else {
30
                lo = mid + 1;
31
            }
32
        }
33
        return ans;
34
    }
35
 
36
    public static void main(String[] args) {
37
        BinaryFloorCeil b = new BinaryFloorCeil();
38
        int[] a = {1, 2, 8, 10, 12, 19};
39
        System.out.println(b.floor(a, 5) + " " + b.ceil(a, 5));
40
    }
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Plain binary search answers 'is x here?'. Floor/ceil answer 'what's the nearest element on this side?' — same halving, but you carry a candidate and lean toward x from one direction. That candidate-carrying tweak is the whole pattern behind lower_bound, upper_bound, and 'search for a boundary' problems generally.

ComplexityO(log n) time, O(1) space — Each comparison halves the range, so O(log n) iterations, each O(1) → O(log n) time and O(1) extra space per query.

E · Edge cases and pitfalls8x smaller than every element — Floor stays -1; ceil is arr[0].Explore edge cases

Edge cases handled

x smaller than every elementFloor stays -1; ceil is arr[0].
x larger than every elementCeil stays -1; floor is arr[n-1].
x present with duplicatesFloor and ceil both equal x; the ≤/≥ comparisons collapse them correctly.
empty arrayLoop never runs → both return the sentinel -1.

Pitfalls

Returning -1 when x isn't present — that's exact-match behaviour, not floor/ceil.
Swapping the kept half between floor and ceil and getting the opposite answer.
Using (lo + hi) / 2 and overflowing on large indices.
Forgetting to initialise the candidate to the sentinel, so a missing floor/ceil reads stale data.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class BinaryFloorCeil { public int floor(int[] arr, int x) { int lo = 0, hi = arr.length - 1, ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public class BinaryFloorCeil {
    public int floor(int[] arr, int x) {
        int lo = 0, hi = arr.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] <= x) {
                ans = arr[mid];   // candidate, then try for a larger valid value
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }

public int ceil(int[] arr, int x) {
        int lo = 0, hi = arr.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] >= x) {
                ans = arr[mid];   // candidate, then try for a smaller valid value
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }

public static void main(String[] args) {
        BinaryFloorCeil b = new BinaryFloorCeil();
        int[] a = {1, 2, 8, 10, 12, 19};
        System.out.println(b.floor(a, 5) + " " + b.ceil(a, 5));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Treating it like exact search

Floor/ceil must return the nearest element on the correct side even when x is absent. Returning -1 just because arr[mid] never equals x defeats the purpose.

Explore the code comparison

Don't write this

if arr[mid] == x:
    return arr[mid]
# ... otherwise eventually return -1 even when a floor exists

Write this instead

if arr[mid] <= x:
    ans = arr[mid]   # keep the best candidate, don't require equality
    lo = mid + 1

Searching the wrong half

For floor you must move right after a hit (to find a larger valid value); for ceil you move left. Swapping them returns the opposite boundary.

Explore the code comparison

Don't write this

// floor, but moving left after a valid candidate
if (arr[mid] <= x) { ans = arr[mid]; hi = mid - 1; } // wrong direction

Write this instead

if (arr[mid] <= x) { ans = arr[mid]; lo = mid + 1; }

Overflow in the midpoint

(lo + hi) can overflow a 32-bit int for large indices, producing a negative mid and out-of-bounds access. Use lo + (hi - lo) / 2.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2; // may overflow

Write this instead

int mid = lo + (hi - lo) / 2;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search for a boundary, keeping the last valid candidate

Code pattern to memorize

FLOOR (largest <= x):
  ans = -1
  while lo <= hi:
    mid = lo + (hi-lo)/2
    if arr[mid] <= x: ans = arr[mid]; lo = mid + 1
    else: hi = mid - 1

CEIL (smallest >= x):
  ans = -1
  while lo <= hi:
    mid = lo + (hi-lo)/2
    if arr[mid] >= x: ans = arr[mid]; hi = mid - 1
    else: lo = mid + 1

Rules to remember

1Floor and ceil are mirror images — same loop, opposite comparison and opposite half to keep.
2Record the candidate the moment it qualifies, then keep searching the side that might do better (smaller gap to x).
3Use mid = lo + (hi - lo) / 2 to avoid integer overflow on lo + hi.
4If x is present, both floor and ceil equal x — the equality in <=/>= handles that for free.
5When nothing qualifies (x below the min for floor, or above the max for ceil), return a sentinel (−1) — don't read out of bounds.

Use this pattern when

Sorted array (or monotone predicate) and you need the nearest element on one side of x
Predecessor/successor queries, nearest-value lookups
Building blocks for insert-position, range counts, and 'closest element' problems
Snapping a query to a discrete grid of allowed values

Choose another pattern when

Array is unsorted → sort first (O(n log n)) or scan; binary search needs order
You need an exact match only → standard binary search returning the index
Data changes a lot between queries → a balanced BST / ordered set gives O(log n) with updates
Tiny array, one query → a linear scan is simpler and fast enough

Interview takeaway

Floor and ceil are the canonical 'binary search for a boundary' pattern: instead of returning on an exact hit, you stash the best candidate and keep narrowing toward x from the correct side. Master this and lower_bound/upper_bound stop being mysterious.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary search for a boundary (lower_bound / upper_bound). Recognise it whenever you need the nearest element on one side of x in sorted data: record the candidate, keep narrowing toward x, return the sentinel when none exists. Floor and ceil are the canonical mirror pair.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Search Insert Position
The ceil's index is exactly where x would be inserted to keep the array sorted (lower_bound).
Find First and Last Position (range)
Coming soon
Lower and upper bound boundaries — the same candidate-carrying binary search, twice.
Closest Element to a Target
Coming soon
Compute floor and ceil, then return whichever is nearer to x.
Count Elements in [a, b]
Coming soon
upper_bound(b) − lower_bound(a) using the same boundary searches.

Same pattern

←

Painter's Partition Problem

Continue · Next problem

Ternary Search on a Unimodal Function

easyBinary SearchFrequently asked

Floor and Ceil in a Sorted Array

Binary Search · 14 of 16 · 9 min

Given a sorted (non-decreasing) array arr and a value x, return the floor of x (the largest element ≤ x) and the ceil of x (the smallest element ≥ x).

If no floor exists (every element is greater than x), return a sentinel such as −1 for the floor. Likewise return −1 for the ceil if no element is ≥ x.

In plain English

Examples

Example 1

Input: arr = [1, 2, 8, 10, 12, 19], x = 5
Output: floor = 2, ceil = 8
Note: Largest element ≤ 5 is 2; smallest element ≥ 5 is 8.

Example 2

Input: arr = [1, 2, 8, 10, 12, 19], x = 10
Output: floor = 10, ceil = 10
Note: x is present, so both floor and ceil are 10.

Example 3

Input: arr = [5, 7, 9], x = 3
Output: floor = -1, ceil = 5
Note: No element ≤ 3 → floor sentinel; smallest ≥ 3 is 5.

Constraints

0 ≤ n ≤ 10⁶, arr sorted in non-decreasing order
Values fit in a 32-bit integer (use long for mid only if indices are huge — here indices fit)
Array may contain duplicates
Return a sentinel (−1) when floor or ceil does not exist

Clarifying questions4First question: What should I return when floor or ceil doesn't exist?Explore questions

Q1.What should I return when floor or ceil doesn't exist?
A sentinel like −1 (or report 'none'). Confirm, because returning the wrong sentinel is a common silent bug.
Q2.Can the array contain duplicates?
Yes. With duplicates equal to x, floor and ceil both equal x; the ≤/≥ comparisons handle it without special cases.
Q3.Is the array guaranteed sorted?
Binary search requires it. If not sorted, you'd sort first (O(n log n)) or scan linearly.
Q4.Do you want the values or their indices?
Either is easy — record the candidate index instead of the value if positions are needed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can adapt plain binary search from 'find an exact match' to 'find the closest element on a given side', tracking a candidate instead of returning immediately.

Where candidates slip

Returning -1 when x isn't present (treating it like exact search), mixing up which half to keep for floor vs ceil, or off-by-one with mid ± 1.

How to stand out

Present floor and ceil as mirror searches, handle the not-found sentinel cleanly, and connect them to lower_bound / upper_bound and insertion position.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(n)`	`O(1)`	Open with this — it makes the definitions concrete and sets up why the sorted order lets us do better.	Read
2	Binary Search for the Boundary (Optimal)Optimal	`O(log n)`	`O(1)`	The intended answer. Stress that you record a candidate and keep searching the better side instead of returning on an exact hit.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(n)SpaceO(1)

Open with this — it makes the definitions concrete and sets up why the sorted order lets us do better.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk the array once. Track the largest value seen that is ≤ x (floor) and, separately, the smallest value that is ≥ x (ceil).

2Hint 2Explore hint

Because the array is sorted you could stop early, but a plain scan ignores that and checks everything.

3Hint 3Explore hint

n comparisons per query — fine for small n, wasteful when n is large or there are many queries.

A · Core idea

The definition-driven baseline simply checks every element.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 8, 10, 12, 19], x = 5

Array state

at 2

2 ≤ 5 → floor = 2

[0]

i ↓

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultfloor = 2, ceil = 8

C · Code with teaching comments

Reference implementation previewpublic class LinearFloorCeil { public int[] floorCeil(int[] arr, int x) { int floor = -1, ceil = -1; for (int v : arr) { if (v <= x) floor = v;Explore the full code

solution.javaJava

Linear Scan — reference

2 teaching notes

1
public class LinearFloorCeil {
2
    public int[] floorCeil(int[] arr, int x) {
3
        int floor = -1, ceil = -1;
4
        for (int v : arr) {
5
            // Sorted order means the last element ≤ x is the floor.
6
            if (v <= x) floor = v;
7
            // The first element ≥ x is the ceil; lock it once.
8
            if (v >= x && ceil == -1) ceil = v;
9
        }
10
        return new int[]{floor, ceil};
11
    }
12
 
13
    public static void main(String[] args) {
14
        int[] r = new LinearFloorCeil().floorCeil(new int[]{1, 2, 8, 10, 12, 19}, 5);
15
        System.out.println(r[0] + " " + r[1]);
16
    }
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The scan's cost comes from ignoring order. Sorted data means 'elements ≤ x' is a contiguous prefix — so the floor is just the last index of that prefix, which binary search finds in O(log n).

ComplexityO(n) time, O(1) space — One pass over n elements with O(1) work each → O(n). Constant extra space for the two candidates.

E · Edge cases and pitfalls3Forgetting the sentinel when no floor/ceil exists.Explore edge cases

Pitfalls

Forgetting the sentinel when no floor/ceil exists.
Overwriting ceil on every match instead of only the first.
Treating O(n) as fine for huge arrays or many repeated queries.

03.2

Approach 2 of 2 · Optimal

Binary Search for the Boundary (Optimal)

TimeO(log n)SpaceO(1)

The intended answer. Stress that you record a candidate and keep searching the better side instead of returning on an exact hit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The elements ≤ x form a prefix of the sorted array; the floor is the last element of that prefix. Binary-search for that boundary.

2Hint 2Explore hint

When arr[mid] ≤ x, mid is a valid floor candidate — record it and search right (lo = mid + 1) for a possibly larger valid value. Otherwise search left.

3Hint 3Explore hint

Ceil mirrors it: when arr[mid] ≥ x, record it and search left (hi = mid − 1) for a smaller valid value; otherwise search right.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 8, 10, 12, 19], x = 5 — compute FLOOR

Array state

mid=2

8 > 5 → discard right half, hi=1

[0]

[1]

mid ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultfloor = 2 (ceil by mirror = 8)

C · Code with teaching comments

solution.javaJava

Binary Search for the Boundary (Optimal) — optimal

5 teaching notes

1
public class BinaryFloorCeil {
2
    public int floor(int[] arr, int x) {
3
        int lo = 0, hi = arr.length - 1, ans = -1;
4
        while (lo <= hi) {
5
            // Overflow-safe midpoint; never compute (lo+hi)/2 for large indices.
6
            int mid = lo + (hi - lo) / 2;
7
            // Floor: arr[mid] qualifies — it's ≤ x.
8
            if (arr[mid] <= x) {
9
                // Stash the candidate and keep searching the right half for something
10
                // closer to x.
11
                ans = arr[mid];   // candidate, then try for a larger valid value
12
                lo = mid + 1;
13
            } else {
14
                // Search left for a smaller value still ≥ x.
15
                hi = mid - 1;
16
            }
17
        }
18
        return ans;
19
    }
20
 
21
    public int ceil(int[] arr, int x) {
22
        int lo = 0, hi = arr.length - 1, ans = -1;
23
        while (lo <= hi) {
24
            int mid = lo + (hi - lo) / 2;
25
            // Ceil mirror: arr[mid] qualifies — it's ≥ x.
26
            if (arr[mid] >= x) {
27
                ans = arr[mid];   // candidate, then try for a smaller valid value
28
                hi = mid - 1;
29
            } else {
30
                lo = mid + 1;
31
            }
32
        }
33
        return ans;
34
    }
35
 
36
    public static void main(String[] args) {
37
        BinaryFloorCeil b = new BinaryFloorCeil();
38
        int[] a = {1, 2, 8, 10, 12, 19};
39
        System.out.println(b.floor(a, 5) + " " + b.ceil(a, 5));
40
    }
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(log n) time, O(1) space — Each comparison halves the range, so O(log n) iterations, each O(1) → O(log n) time and O(1) extra space per query.

E · Edge cases and pitfalls8x smaller than every element — Floor stays -1; ceil is arr[0].Explore edge cases

Edge cases handled

x smaller than every elementFloor stays -1; ceil is arr[0].
x larger than every elementCeil stays -1; floor is arr[n-1].
x present with duplicatesFloor and ceil both equal x; the ≤/≥ comparisons collapse them correctly.
empty arrayLoop never runs → both return the sentinel -1.

Pitfalls

Returning -1 when x isn't present — that's exact-match behaviour, not floor/ceil.
Swapping the kept half between floor and ceil and getting the opposite answer.
Using (lo + hi) / 2 and overflowing on large indices.
Forgetting to initialise the candidate to the sentinel, so a missing floor/ceil reads stale data.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Treating it like exact search

Floor/ceil must return the nearest element on the correct side even when x is absent. Returning -1 just because arr[mid] never equals x defeats the purpose.

Explore the code comparison

Don't write this

if arr[mid] == x:
    return arr[mid]
# ... otherwise eventually return -1 even when a floor exists

Write this instead

if arr[mid] <= x:
    ans = arr[mid]   # keep the best candidate, don't require equality
    lo = mid + 1

Searching the wrong half

For floor you must move right after a hit (to find a larger valid value); for ceil you move left. Swapping them returns the opposite boundary.

Explore the code comparison

Don't write this

// floor, but moving left after a valid candidate
if (arr[mid] <= x) { ans = arr[mid]; hi = mid - 1; } // wrong direction

Write this instead

if (arr[mid] <= x) { ans = arr[mid]; lo = mid + 1; }

Overflow in the midpoint

(lo + hi) can overflow a 32-bit int for large indices, producing a negative mid and out-of-bounds access. Use lo + (hi - lo) / 2.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2; // may overflow

Write this instead

int mid = lo + (hi - lo) / 2;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search for a boundary, keeping the last valid candidate

Code pattern to memorize

FLOOR (largest <= x):
  ans = -1
  while lo <= hi:
    mid = lo + (hi-lo)/2
    if arr[mid] <= x: ans = arr[mid]; lo = mid + 1
    else: hi = mid - 1

CEIL (smallest >= x):
  ans = -1
  while lo <= hi:
    mid = lo + (hi-lo)/2
    if arr[mid] >= x: ans = arr[mid]; hi = mid - 1
    else: lo = mid + 1

Rules to remember

1Floor and ceil are mirror images — same loop, opposite comparison and opposite half to keep.
2Record the candidate the moment it qualifies, then keep searching the side that might do better (smaller gap to x).
3Use mid = lo + (hi - lo) / 2 to avoid integer overflow on lo + hi.
4If x is present, both floor and ceil equal x — the equality in <=/>= handles that for free.
5When nothing qualifies (x below the min for floor, or above the max for ceil), return a sentinel (−1) — don't read out of bounds.

Use this pattern when

Sorted array (or monotone predicate) and you need the nearest element on one side of x
Predecessor/successor queries, nearest-value lookups
Building blocks for insert-position, range counts, and 'closest element' problems
Snapping a query to a discrete grid of allowed values

Choose another pattern when

Array is unsorted → sort first (O(n log n)) or scan; binary search needs order
You need an exact match only → standard binary search returning the index
Data changes a lot between queries → a balanced BST / ordered set gives O(log n) with updates
Tiny array, one query → a linear scan is simpler and fast enough

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Search Insert Position
The ceil's index is exactly where x would be inserted to keep the array sorted (lower_bound).
Find First and Last Position (range)
Coming soon
Lower and upper bound boundaries — the same candidate-carrying binary search, twice.
Closest Element to a Target
Coming soon
Compute floor and ceil, then return whichever is nearer to x.
Count Elements in [a, b]
Coming soon
upper_bound(b) − lower_bound(a) using the same boundary searches.

Same pattern

←

Painter's Partition Problem

Continue · Next problem

Ternary Search on a Unimodal Function