Floor and Ceil in Sorted Array in DSA Java

Mental Model

Find the closest smaller or equal value (floor) and closest greater or equal value (ceil) to a target in a sorted list.

Analogy: Imagine standing on a number line with houses at certain addresses. Floor is the nearest house at or before your position, ceil is the nearest house at or after your position.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: 5 (nearest smaller or equal)
Ceil: 7 (nearest greater or equal)

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target: 6

Goal: Find floor and ceil values for 6 in the array

Step 1: Start binary search with low=0, high=4

Array: [1, 3, 5, 7, 9]
low=0, high=4

Why: We begin searching the whole array to find floor and ceil

Step 2: Calculate mid=2, array[mid]=5; 5 < 6, so floor candidate updated to 5, move low to mid+1=3

Floor=5
low=3, high=4

Why: 5 is less than target, so it can be floor; search right half for closer values

Step 3: Calculate mid=3, array[mid]=7; 7 > 6, so ceil candidate updated to 7, move high to mid-1=2

Floor=5, Ceil=7
low=3, high=2

Why: 7 is greater than target, so it can be ceil; search left half for closer values

Step 4: Since low > high, stop search

Floor=5, Ceil=7

Why: Search ends when low passes high; floor and ceil found

Result:

Floor: 5
Ceil: 7

Annotated Code

DSA Java

public class FloorCeil {
    public static int floor(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int floor = -1; // -1 means no floor found yet
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return arr[mid]; // exact match is floor and ceil
            } else if (arr[mid] < target) {
                floor = arr[mid]; // update floor candidate
                low = mid + 1; // search right half
            } else {
                high = mid - 1; // search left half
            }
        }
        return floor;
    }

    public static int ceil(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int ceil = -1; // -1 means no ceil found yet
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return arr[mid]; // exact match is floor and ceil
            } else if (arr[mid] > target) {
                ceil = arr[mid]; // update ceil candidate
                high = mid - 1; // search left half
            } else {
                low = mid + 1; // search right half
            }
        }
        return ceil;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 6;
        int floorValue = floor(arr, target);
        int ceilValue = ceil(arr, target);
        System.out.println("Floor: " + floorValue);
        System.out.println("Ceil: " + ceilValue);
    }
}

while (low <= high) {

loop to narrow search range until low passes high

int mid = low + (high - low) / 2;

calculate middle index to check

if (arr[mid] == target) { return arr[mid]; }

exact match found, return immediately

else if (arr[mid] < target) { floor = arr[mid]; low = mid + 1; }

update floor candidate and search right half

else { high = mid - 1; }

search left half when mid value is greater than target

Output

Floor: 5

Ceil: 7

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans entire array O(n), binary search is faster for sorted arrays

Edge Cases

target smaller than all array elements

floor returns -1 (no smaller or equal), ceil returns smallest element

DSA Java

int floor = -1; // -1 means no floor found yet

target greater than all array elements

floor returns largest element, ceil returns -1 (no greater or equal)

DSA Java

int ceil = -1; // -1 means no ceil found yet

target exactly matches an element

floor and ceil both return that element immediately

DSA Java

if (arr[mid] == target) { return arr[mid]; }

When to Use This Pattern

When you need closest smaller or equal and closest greater or equal values in a sorted list, use binary search for floor and ceil to find them efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidates when moving search boundaries
Fix: Always update floor when arr[mid] < target and update ceil when arr[mid] > target before moving boundaries

Summary

Finds the closest smaller or equal (floor) and closest greater or equal (ceil) values to a target in a sorted array.

Use when you want quick lookups of nearest values around a target in sorted data.

The key insight is to use binary search to narrow down candidates efficiently by updating floor and ceil during the search.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The greatest element less than or equal to the number

B. The smallest element greater than the number

C. The average of all elements less than the number

D. The smallest element less than the number

Solution

1. Step 1: Understand floor definition in sorted array

   The floor of a number is the greatest element in the array that is less than or equal to the number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly, others describe different concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option A

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ target, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is strictly less than the number
• Mixing floor with average or median

2. Which of the following is the correct Java method signature to find the floor of a number in a sorted integer array?

easy

A. int findFloor(int arr[], target)

B. public int findFloor(int[] arr, int target, int size)

C. static int findFloor(int[] arr, int target) throws Exception

D. public static int findFloor(int[] arr, int target)

Solution

1. Step 1: Check Java method signature syntax

   Java methods must specify access modifier, return type, method name, and parameter types.

2. Step 2: Validate each option

   public static int findFloor(int[] arr, int target) is correct: public static int findFloor(int[] arr, int target). int findFloor(int arr[], target) misses access modifier and parameter type for target. static int findFloor(int[] arr, int target) throws Exception unnecessarily throws Exception. public int findFloor(int[] arr, int target, int size) has extra parameter 'size' not needed.

3. Final Answer:

   public static int findFloor(int[] arr, int target) -> Option D

4. Quick Check:

   Correct Java method signature = public static int findFloor(int[] arr, int target) [OK]

Hint: Java method needs access modifier, return type, parameters [OK]

Common Mistakes:

• Omitting access modifier
• Missing parameter types
• Adding unnecessary throws clause

3. Given the sorted array int[] arr = {1, 3, 5, 7, 9} and target = 6, what is the floor and ceil of 6?

medium

A. Floor = 7, Ceil = 9

B. Floor = 3, Ceil = 5

C. Floor = 5, Ceil = 7

D. Floor = 6, Ceil = 6

Solution

1. Step 1: Identify floor of 6 in array

   Floor is greatest element ≤ 6. Elements ≤ 6 are 1, 3, 5. Greatest is 5.

2. Step 2: Identify ceil of 6 in array

   Ceil is smallest element ≥ 6. Elements ≥ 6 are 7, 9. Smallest is 7.

3. Final Answer:

   Floor = 5, Ceil = 7 -> Option C

4. Quick Check:

   Floor ≤ 6 = 5, Ceil ≥ 6 = 7 [OK]

Hint: Floor ≤ target, ceil ≥ target; pick closest values [OK]

Common Mistakes:

• Choosing floor greater than target
• Choosing ceil less than target
• Assuming target must be in array

4. Consider this Java method to find floor in a sorted array:

public static int findFloor(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int floor = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return arr[mid];
        else if (arr[mid] < target) {
            floor = arr[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return floor;
}

What is the bug if the array is empty?

medium

A. Returns -1 correctly as floor does not exist

B. Throws ArrayIndexOutOfBoundsException at mid calculation

C. Returns 0 incorrectly as floor

D. Infinite loop occurs

Solution

1. Step 1: Analyze behavior with empty array

   If array is empty, arr.length = 0, so high = -1. Condition low <= high is false initially, so loop never runs.

2. Step 2: Check return value when loop doesn't run

   Variable floor initialized to -1 and returned as is, indicating no floor found.

3. Final Answer:

   Returns -1 correctly as floor does not exist -> Option A

4. Quick Check:

   Empty array returns -1 floor [OK]

Hint: Check loop condition before accessing array [OK]

Common Mistakes:

• Assuming mid calculation causes error on empty array
• Expecting exception instead of -1 return
• Missing initialization of floor variable

5. You have a sorted array int[] arr = {2, 4, 6, 8, 10}. You want to find the floor and ceil for target = 1 and target = 11. What are the correct floor and ceil values for these targets?

hard

A. For 1: Floor = -1, Ceil = 2; For 11: Floor = -1, Ceil = -1

B. For 1: Floor = -1, Ceil = 2; For 11: Floor = 10, Ceil = -1

C. For 1: Floor = -1, Ceil = -1; For 11: Floor = 10, Ceil = 10

D. For 1: Floor = 2, Ceil = -1; For 11: Floor = -1, Ceil = 10

Solution

1. Step 1: Find floor and ceil for target = 1

   Floor is greatest element ≤ 1. No elements ≤ 1, so floor = -1 (not found). Ceil is smallest element ≥ 1, which is 2.

2. Step 2: Find floor and ceil for target = 11

   Floor is greatest element ≤ 11, which is 10. Ceil is smallest element ≥ 11, none exists, so ceil = -1.

3. Final Answer:

   For 1: Floor = -1, Ceil = 2; For 11: Floor = 10, Ceil = -1 -> Option B

4. Quick Check:

   Floor and ceil outside array bounds handled with -1 [OK]

Hint: Floor or ceil missing means return -1 for that value [OK]

Common Mistakes:

• Returning array ends incorrectly as floor or ceil
• Confusing floor and ceil for out-of-bound targets
• Assuming floor or ceil always exists