Definition
- Ceiling – the smallest array element that is greater than or equal to the given key.
- Edge case – if the key is greater than the last element, no ceiling exists; return minus one.
- Binary search – standard loop; if
key < arr[mid], moveend = mid - 1; ifkey > arr[mid], movestart = mid + 1; if equal, returnmid. - Convergence – when the loop ends,
startpoints to the ceiling index because all elements below the key have been discarded. - Complexity – O(log n) time, O(1) space.
At the National Bank of India, loan interest slabs are stored in ascending order. When Priya requests a loan amount that falls between two slab boundaries, policy requires charging the next slab at or above her amount. Binary-searching the slab list and returning the element at the start pointer gives exactly the ceiling slab.
Understanding the Concepts
What is the ceiling of a number?
The ceiling of a key in a sorted array is the smallest element that is greater than or equal to the key. If the key itself exists in the array, it is its own ceiling. If the key is larger than every element, no ceiling exists.
package com.bank.core;
public class CeilingOfNumber {
public static int findCeiling(int[] arr, int key) {
if (key > arr[arr.length - 1]) return -1;
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) return mid;
if (key < arr[mid]) end = mid - 1;
else start = mid + 1;
}
return start; // start points to the ceiling
}
public static void main(String[] args) {
int[] slabs = {1000, 3000, 8000, 10000, 15000};
System.out.println("Ceiling of 5000: index " + findCeiling(slabs, 5000)
+ " value " + slabs[findCeiling(slabs, 5000)]);
System.out.println("Ceiling of 8000: index " + findCeiling(slabs, 8000));
System.out.println("Ceiling of 20000: " + findCeiling(slabs, 20000));
}
}
Ceiling of 5000: index 2 value 8000
Ceiling of 8000: index 2
Ceiling of 20000: -1
Why does the start pointer land on the ceiling?
During binary search, every time start moves right it discards an element smaller than the key. Every time end moves left it keeps elements at or above the key. When the loop ends with start > end, start is the first position where arr[start] >= key, which is the ceiling.
package com.bank.core;
public class CeilingConvergence {
public static void main(String[] args) {
int[] arr = {1000, 3000, 8000, 10000, 15000};
int key = 5000;
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
System.out.println("start=" + start + " end=" + end + " mid=" + mid
+ " arr[mid]=" + arr[mid]);
if (arr[mid] == key) { System.out.println("Found!"); return; }
if (key < arr[mid]) end = mid - 1;
else start = mid + 1;
}
System.out.println("Ceiling at start=" + start + ": " + arr[start]);
}
}
start=0 end=4 mid=2 arr[mid]=8000
start=0 end=1 mid=0 arr[mid]=1000
start=1 end=1 mid=1 arr[mid]=3000
Ceiling at start=2: 8000
What is the floor and how does it relate?
The floor of a key is the largest element less than or equal to the key. It is the mirror of the ceiling. When binary search ends, end points to the floor index. Knowing both invariants, start-on-ceiling and end-on-floor, gives complete command of the pattern.
package com.bank.core;
public class FloorOfNumber {
public static int findFloor(int[] arr, int key) {
if (key < arr[0]) return -1;
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) return mid;
if (key < arr[mid]) end = mid - 1;
else start = mid + 1;
}
return end; // end points to the floor
}
public static void main(String[] args) {
int[] slabs = {1000, 3000, 8000, 10000, 15000};
int floorIdx = findFloor(slabs, 5000);
System.out.println("Floor of 5000: index " + floorIdx + " value " + slabs[floorIdx]);
}
}
Floor of 5000: index 1 value 3000
How is ceiling used in slab-based lookups?
In banking, interest rates are assigned by slabs. Given a loan amount, the ceiling slab determines the applicable rate. This is a direct application of the ceiling algorithm.
package com.bank.core;
import java.math.BigDecimal;
public class InterestSlabLookup {
public static int findCeiling(int[] slabs, int amount) {
if (amount > slabs[slabs.length - 1]) return -1;
int start = 0, end = slabs.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (slabs[mid] == amount) return mid;
if (amount < slabs[mid]) end = mid - 1;
else start = mid + 1;
}
return start;
}
public static void main(String[] args) {
int[] slabs = {50000, 100000, 500000, 1000000};
BigDecimal[] rates = {
new BigDecimal("8.5"), new BigDecimal("9.0"),
new BigDecimal("10.5"), new BigDecimal("12.0")
};
int loanAmount = 75000;
int slabIdx = findCeiling(slabs, loanAmount);
System.out.println("Loan: " + loanAmount + " → Slab: " + slabs[slabIdx]
+ " Rate: " + rates[slabIdx] + "%");
}
}
Loan: 75000 → Slab: 100000 Rate: 9.0%
What are the edge cases?
Edge cases include the key being smaller than the first element (ceiling is the first element), the key matching an element exactly, and the key exceeding the last element.
package com.bank.core;
public class CeilingEdgeCases {
public static int findCeiling(int[] arr, int key) {
if (key > arr[arr.length - 1]) return -1;
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) return mid;
if (key < arr[mid]) end = mid - 1;
else start = mid + 1;
}
return start;
}
public static void main(String[] args) {
int[] arr = {1000, 3000, 8000, 10000};
System.out.println("Below min (500): " + findCeiling(arr, 500));
System.out.println("Exact match (3000): " + findCeiling(arr, 3000));
System.out.println("Above max (20000): " + findCeiling(arr, 20000));
System.out.println("Between (5000): " + findCeiling(arr, 5000));
}
}
Below min (500): 0
Exact match (3000): 1
Above max (20000): -1
Between (5000): 2
What are common mistakes?
The most common mistake is forgetting the edge case where the key exceeds the last element, causing start to go out of bounds. Always check this before the loop.
How does this relate to Java's Arrays.binarySearch?
Java's Arrays.binarySearch returns -(insertion point) - 1 when the key is not found. The insertion point is exactly the ceiling index. So int ip = -(result) - 1 gives the same answer as our ceiling algorithm.
package com.bank.core;
import java.util.Arrays;
public class JavaBinarySearchCeiling {
public static void main(String[] args) {
int[] arr = {1000, 3000, 8000, 10000, 15000};
int result = Arrays.binarySearch(arr, 5000);
if (result >= 0) {
System.out.println("Found at: " + result);
} else {
int insertionPoint = -(result) - 1;
System.out.println("Ceiling index: " + insertionPoint
+ " value: " + arr[insertionPoint]);
}
}
}
Ceiling index: 2 value: 8000
What should a senior engineer know?
A senior engineer should understand both the start-on-ceiling and end-on-floor invariants, explain why each movement preserves or discards candidates, and know that Java's built-in Arrays.binarySearch encodes the ceiling position in its negative return value. Recognizing these invariants is the key insight for the Modified Binary Search pattern.
Visual Overview
Array: [1000, 3000, 8000, 10000, 15000] Key: 5000 Step 1: start=0 end=4 mid=2 arr[2]=8000 > key → end = 1 (keep elements >= key on left) Step 2: start=0 end=1 mid=0 arr[0]=1000 < key → start = 1 (discard elements < key) Step 3: start=1 end=1 mid=1 arr[1]=3000 < key → start = 2 (discard elements < key) Loop ends: start=2 > end=1 → Ceiling at index 2: arr[2] = 8000 ┌──────────────────────────────────────────┐ │ [1000, 3000, 8000, 10000, 15000] │ │ ↑end ↑start │ │ ↑ ceiling = 8000 │ │ │ │ start always lands on the ceiling │ │ end always lands on the floor │ └──────────────────────────────────────────┘
Key Takeaway
Ceiling of a number is a Modified Binary Search variant where the goal is the smallest array element greater than or equal to the key. The algorithm is standard binary search with one key insight: when the loop ends with start past end, the start pointer sits exactly on the ceiling. That is because every leftward move of end preserves candidates at or above the key, while every rightward move of start discards elements below the key.
The edge case to handle first is when the key exceeds the last element, because then no ceiling exists and start would go out of bounds. An exact match returns immediately. The mirror problem, the floor, works identically except the end pointer lands on the answer after the loop.
In Priya's work at the National Bank of India, this pattern drives interest rate slab lookups. When her loan amount falls between two slab boundaries, policy charges the next slab at or above the amount, which is the ceiling. Binary-searching the ascending slab table finds the correct slab in logarithmic time.
Knowing both the start-on-ceiling and end-on-floor invariants gives complete command of Modified Binary Search convergence. Java's Arrays.binarySearch encodes the ceiling position in its negative return value, which is the same invariant expressed differently.
Remember one sentence: after binary search misses, the start pointer sits on the ceiling and the end pointer sits on the floor.
---