PPractick

The problem

A shipping company prices parcels in fixed weight bands, stored as a sorted array of band limits. For a parcel of weight x, the billing system needs the floor (the largest band limit ≤ x, the band already reached) and the ceil (the smallest band limit ≥ x, the band to charge for). If there is no such value, it reports -1. Both are one binary search each: floor is "last index with value ≤ x" and ceil is the lower bound.

Example: [3, 4, 4, 7, 8, 10], x = 5 → floor 4, ceil 7.

Function signature

pair<int, int> floorAndCeil(const vector<int>& a, int x);  // {floor value, ceil value}; -1 if absent

Test cases

Input (a, x)	Output	Explanation
([3, 4, 4, 7, 8, 10], 5)	{4, 7}	5 lies between 4 and 7
([3, 4, 4, 7, 8, 10], 8)	{8, 8}	x itself is present
([3, 4, 4, 7, 8, 10], 2)	{-1, 3}	No value ≤ 2
([3, 4, 4, 7, 8, 10], 11)	{10, -1}	No value ≥ 11
([5], 5)	{5, 5}

(Confirm: the array is sorted; values are positive, so -1 unambiguously means "does not exist".)

How interviewers phrase it

• "Find the floor and ceil of X in a sorted array" (GeeksforGeeks).
• Sometimes asked as indices rather than values.
• The same idea powers TreeMap.floorKey / ceilingKey in Java and lower_bound in C++.

Clarifying questions to ask

1. Return values or indices?
2. What should be returned when the floor or ceil doesn't exist?
3. Can the array contain duplicates?

Follow-ups to expect

1. "How is floor computed?"
2. "And ceil?"
3. "How are they related to upper bound?"
4. "What if the data changes often?"
5. "Complexity?"

Related questions

• Search X in sorted array Easy
• Lower Bound Easy
• Upper Bound Easy
• Search insert position Easy
• Count Occurrences in a Sorted Array Easy
• Kth Missing Positive Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in