Find the Floor and Ceiling of a Number in a Sorted Array

Easy15–20 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftAdobe

Given an array nums sorted in non-decreasing order and an integer target, return [floor, ceil] — the largest value ≤ target and the smallest value ≥ target. Use -1 for either one if it doesn't exist. Solve it in O(log n) time: as the binary search narrows in on target, every comparison either tightens the floor or the ceiling, so a single pass finds both.

Test Case 1:

Input:nums = [1, 2, 8, 10, 10, 12, 19], target = 5

Output:[2, 8]

Explanation:2 is the largest value ≤ 5 (floor); 8 is the smallest value ≥ 5 (ceil).

Test Case 2:

Input:nums = [1, 2, 8, 10, 10, 12, 19], target = 10

Output:[10, 10]

Explanation:10 is present, so it's both its own floor and ceiling.

Test Case 3:

Input:nums = [1, 8, 10], target = 5

Output:[1, 8]

Explanation:1 is the floor, 8 is the ceiling.

Constraints

◆1 ≤ nums.length ≤ 10⁴
◆0 ≤ nums[i] ≤ 10⁵ (all values non-negative, so -1 unambiguously means "none")
◆-10⁵ ≤ target ≤ 10⁵
◆nums is sorted in non-decreasing order (duplicates are allowed)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (sorted, comma-separated) — 1-12 non-negative integers, sorted ascendingtarget

1	class Solution {
2	public int[] floorCeil(int[] nums, int target) {
3	int lo = 0, hi = nums.length - 1, floorVal = -1, ceilVal = -1;
4	while (lo <= hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] == target) {
7	floorVal = nums[mid];
8	ceilVal = nums[mid];
9	break;
10	} else if (nums[mid] < target) {
11	floorVal = nums[mid];
12	lo = mid + 1;
13	} else {
14	ceilVal = nums[mid];
15	hi = mid - 1;
16	}
17	}
18	return new int[]{floorVal, ceilVal};
19	}
20	}
21

↑lo

↑hi

Variables

lo0

hi2

floorVal-1

ceilVal-1

INITIALIZE

Binary search [0, 2] for target 5, tracking the largest value ≤ target (floor) and smallest value ≥ target (ceil) as we narrow in.

Step 1 / 4

Approach & Solutions

Brute Force — Linear Scan

Brute

Scan once, left to right. Every value ≤ target is a candidate floor — since the array is sorted, the last one you see is the largest, so just keep overwriting it. The first value ≥ target you encounter is the ceiling — record it once and stop updating it. Correct on any array, but it checks every element instead of jumping straight to the answer.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public int[] floorCeil(int[] nums, int target) {
        int floorVal = -1, ceilVal = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= target) floorVal = nums[i];
            if (nums[i] >= target && ceilVal == -1) ceilVal = nums[i];
        }
        return new int[]{floorVal, ceilVal};
    }
}

Optimal — Binary Search

Optimal

Binary search toward target, tracking the best floor and ceil seen so far. Whenever nums[mid] is below target, it's a new floor candidate (closer than any found before) — record it and search right for something even closer. Whenever it's above target, it's a new ceil candidate — record it and search left. An exact match is trivially both.

TimeO(log n)