Floor and Ceil in Sorted Array

Given a sorted array of integers and a target number x, your task is to find the floor and ceil of x in the array.

• The floor of x is the greatest number in the array that is less than or equal to x.
• The ceil of x is the smallest number in the array that is greater than or equal to x.

If the floor or ceil does not exist, return -1 for that value.

Understanding the Problem

We are given a sorted array and a number x. Our task is to find two special values:

• Floor – the largest number in the array that is less than or equal to x.
• Ceiling – the smallest number in the array that is greater than or equal to x.

This means we’re looking for the closest values that "hug" x from below and above. The solution must work efficiently, especially for large arrays.

Step-by-Step Plan Using an Example

Example

Here, floor(6) should be 5 and ceiling(6) should be 7.

Step 1: Use Binary Search

Since the array is sorted, we’ll use binary search to reduce our work by half at every step.

We maintain two pointers: low and high. At each step, we calculate mid and compare the middle element with x.

Step 2: Apply the Three Cases

• If arr[mid] == x → We found an exact match. Both floor and ceiling are x.
• If arr[mid] < x → This could be a floor. We move low = mid + 1.
• If arr[mid] > x → This could be a ceiling. We move high = mid - 1.

Step 3: Track Closest Values

During the search, we keep updating two variables:

• floor gets updated when we find a number ≤ x
• ceiling gets updated when we find a number ≥ x

Final Result

When the loop ends, floor and ceiling will hold our answers.

Incorporating Edge Cases

Let’s handle some special situations:

• If x is smaller than all elements in the array → floor doesn’t exist, only ceiling.
• If x is greater than all elements → ceiling doesn’t exist, only floor.
• If x exactly matches an element → both floor and ceiling are x.

Our code needs to check and return null or a special value (like -1) when a floor or ceiling doesn’t exist.

Why Binary Search Works

Binary Search divides the search space in half at every step, so it runs in O(log n) time. This makes it very efficient for large arrays.

Since the array is sorted, we never miss any candidates—we just have to make the right decisions at each midpoint.

Beginner Tip

Always test your algorithm with:

• Values smaller than the first element
• Values larger than the last element
• Values in the middle
• Exact matches

This builds confidence that your logic is covering all edge cases.

1. Given a sorted array arr and a target value x.
2. Initialize floor = -1 and ceil = -1.
3. Use binary search to find floor:
4. → While low ≤ high, compute mid.
5. → If arr[mid] == x, both floor and ceil are arr[mid]. Return.
6. → If arr[mid] < x, update floor = arr[mid], search right.
7. → If arr[mid] > x, update ceil = arr[mid], search left.
8. Continue until low > high.
9. Return the computed floor and ceil.

#include <stdio.h>

void findFloorCeil(int arr[], int n, int x, int* floor, int* ceil) {
    int low = 0, high = n - 1;
    *floor = -1;
    *ceil = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            *floor = *ceil = arr[mid];
            return;
        } else if (arr[mid] < x) {
            *floor = arr[mid];
            low = mid + 1;
        } else {
            *ceil = arr[mid];
            high = mid - 1;
        }
    }
}

int main() {
    int arr[] = {1, 2, 4, 6, 10, 12};
    int x = 5, floor, ceil;
    int n = sizeof(arr) / sizeof(arr[0]);
    findFloorCeil(arr, n, x, &floor, &ceil);
    printf("Floor: %d, Ceil: %d\n", floor, ceil);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findFloorCeil(vector<int>& arr, int x) {
    int low = 0, high = arr.size() - 1;
    int floor = -1, ceil = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x)
            return {arr[mid], arr[mid]};
        else if (arr[mid] < x) {
            floor = arr[mid];
            low = mid + 1;
        } else {
            ceil = arr[mid];
            high = mid - 1;
        }
    }

    return {floor, ceil};
}

int main() {
    vector<int> arr = {1, 2, 4, 6, 10, 12};
    int x = 5;
    auto result = findFloorCeil(arr, x);
    cout << "Floor: " << result.first << ", Ceil: " << result.second << endl;
    return 0;
}

def find_floor_ceil(arr, x):
    low, high = 0, len(arr) - 1
    floor, ceil = -1, -1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return arr[mid], arr[mid]
        elif arr[mid] < x:
            floor = arr[mid]
            low = mid + 1
        else:
            ceil = arr[mid]
            high = mid - 1

    return floor, ceil

arr = [1, 2, 4, 6, 10, 12]
x = 5
print("Floor and Ceil:", find_floor_ceil(arr, x))

public class FloorCeilFinder {
    public static int[] findFloorCeil(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int floor = -1, ceil = -1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == x) {
                return new int[]{arr[mid], arr[mid]};
            } else if (arr[mid] < x) {
                floor = arr[mid];
                low = mid + 1;
            } else {
                ceil = arr[mid];
                high = mid - 1;
            }
        }
        return new int[]{floor, ceil};
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 10, 12};
        int x = 5;
        int[] result = findFloorCeil(arr, x);
        System.out.println("Floor: " + result[0] + ", Ceil: " + result[1]);
    }
}

function findFloorCeil(arr, x) {
    let low = 0, high = arr.length - 1;
    let floor = -1, ceil = -1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === x) {
            return [arr[mid], arr[mid]];
        } else if (arr[mid] < x) {
            floor = arr[mid];
            low = mid + 1;
        } else {
            ceil = arr[mid];
            high = mid - 1;
        }
    }
    return [floor, ceil];
}

const arr = [1, 2, 4, 6, 10, 12];
const x = 5;
console.log("Floor and Ceil:", findFloorCeil(arr, x));

package main

import (
    "fmt"
)

func findFloorCeil(arr []int, x int) (int, int) {
    low, high := 0, len(arr)-1
    floor, ceil := -1, -1

    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == x {
            return arr[mid], arr[mid]
        } else if arr[mid] < x {
            floor = arr[mid]
            low = mid + 1
        } else {
            ceil = arr[mid]
            high = mid - 1
        }
    }
    return floor, ceil
}

func main() {
    arr := []int{1, 2, 4, 6, 10, 12}
    x := 5
    floor, ceil := findFloorCeil(arr, x)
    fmt.Printf("Floor: %d, Ceil: %d\n", floor, ceil)
}

fn find_floor_ceil(arr: &Vec<i32>, x: i32) -> (i32, i32) {
    let (mut low, mut high) = (0, arr.len() as i32 - 1);
    let (mut floor, mut ceil) = (-1, -1);

    while low <= high {
        let mid = (low + high) / 2;
        let mid_val = arr[mid as usize];

        if mid_val == x {
            return (x, x);
        } else if mid_val < x {
            floor = mid_val;
            low = mid + 1;
        } else {
            ceil = mid_val;
            high = mid - 1;
        }
    }
    (floor, ceil)
}

fn main() {
    let arr = vec![1, 2, 4, 6, 10, 12];
    let x = 5;
    let (floor, ceil) = find_floor_ceil(&arr, x);
    println!("Floor: {}, Ceil: {}", floor, ceil);
}

fun findFloorCeil(arr: IntArray, x: Int): Pair<Int, Int> {
    var low = 0
    var high = arr.size - 1
    var floor = -1
    var ceil = -1

    while (low <= high) {
        val mid = (low + high) / 2
        if (arr[mid] == x) {
            return Pair(arr[mid], arr[mid])
        } else if (arr[mid] < x) {
            floor = arr[mid]
            low = mid + 1
        } else {
            ceil = arr[mid]
            high = mid - 1
        }
    }
    return Pair(floor, ceil)
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 6, 10, 12)
    val x = 5
    val result = findFloorCeil(arr, x)
    println("Floor: ${result.first}, Ceil: ${result.second}")
}

func findFloorCeil(arr: [Int], x: Int) -> (Int, Int) {
    var low = 0, high = arr.count - 1
    var floor = -1, ceil = -1

    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] == x {
            return (x, x)
        } else if arr[mid] < x {
            floor = arr[mid]
            low = mid + 1
        } else {
            ceil = arr[mid]
            high = mid - 1
        }
    }
    return (floor, ceil)
}

let arr = [1, 2, 4, 6, 10, 12]
let x = 5
let result = findFloorCeil(arr: arr, x: x)
print("Floor: \(result.0), Ceil: \(result.1)")

function findFloorCeil(arr: number[], x: number): [number, number] {
    let low = 0, high = arr.length - 1;
    let floor = -1, ceil = -1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === x) {
            return [x, x];
        } else if (arr[mid] < x) {
            floor = arr[mid];
            low = mid + 1;
        } else {
            ceil = arr[mid];
            high = mid - 1;
        }
    }
    return [floor, ceil];
}

const arr = [1, 2, 4, 6, 10, 12];
const x = 5;
const [floor, ceil] = findFloorCeil(arr, x);
console.log(`Floor: ${floor}, Ceil: ${ceil}`);

Time complexity

Space complexity

O(1)

The algorithm operates using a constant number of variables (like low, high, mid, floor, ceil), without requiring additional memory.