☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Floor and Ceil in Sorted Array

Easy TUF ID 86 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr sorted in non-decreasing order and an integer x. Find two values:

Return them as a pair {floor, ceil}. If one of them does not exist (no element small enough, or no element large enough), report -1 in its place. If x itself is present, both floor and ceil equal x.

Constraints: 0 ≤ n ≤ 10^5, values and x fit in a 32-bit signed integer. The problem uses -1 as the “missing” marker, which implicitly assumes non-negative values; with negative data you would use a different sentinel (for example Integer.MIN_VALUE) or return a flag.

Example 1

arr = [3, 4, 4, 7, 8, 10], x = 5
answer = [4, 7]           // 4 is the largest value <= 5, 7 is the smallest value >= 5

Example 2

arr = [3, 4, 4, 7, 8, 10], x = 4
answer = [4, 4]           // x is present, so it is its own floor and ceil

Example 3

arr = [3, 4, 4, 7, 8, 10], x = 2
answer = [-1, 3]          // nothing is <= 2, so there is no floor

Approach 1: Brute force, one linear pass

Intuition. Walk the array once. Every value <= x is a floor candidate, and because values only grow, the last candidate we see is the largest, so we can simply overwrite floor each time. The first value >= x is the smallest such value, so the moment we see one we record it as ceil and stop; everything after it is at least as large.

Algorithm.

  1. Set floor = -1, ceil = -1.
  2. For each value v in order:
    • If v <= x, set floor = v.
    • If v >= x, set ceil = v and stop scanning.
  3. Return {floor, ceil}.
static int[] bruteForce(int[] arr, int x) {
    int floor = -1, ceil = -1;
    for (int v : arr) {
        if (v <= x) floor = v;             // values only grow, so the last one <= x is the floor
        if (v >= x) { ceil = v; break; }   // the first value >= x is the smallest such value
    }
    return new int[]{floor, ceil};
}

Complexity. Time O(n): at most one pass. Space O(1).

When v == x both conditions fire in the same iteration: floor becomes x, then ceil becomes x and we break, which is exactly Example 2.

Approach 2: Optimal, two binary searches

Intuition. Each of the two answers is a “first/last element satisfying a monotone predicate” question on a sorted array, so each can be found by its own binary search.

Both searches start with ans = -1 so that “no qualifying element” falls out naturally.

Algorithm.

  1. Floor search: lo = 0, hi = n - 1, ans = -1. While lo <= hi: if arr[mid] <= x, set ans = arr[mid] and lo = mid + 1; else hi = mid - 1.
  2. Ceil search: same shape with the predicate arr[mid] >= x, recording ans = arr[mid] and moving left via hi = mid - 1; otherwise lo = mid + 1.
  3. Return {floorAns, ceilAns}.
static int[] optimal(int[] arr, int x) {
    return new int[]{floorBinarySearch(arr, x), ceilBinarySearch(arr, x)};
}

private static int floorBinarySearch(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= x) {
            ans = arr[mid];       // candidate; a larger qualifying value may exist on the right
            lo = mid + 1;
        } else {
            hi = mid - 1;         // arr[mid] > x, so everything from mid onward is too big
        }
    }
    return ans;
}

private static int ceilBinarySearch(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) {
            ans = arr[mid];       // candidate; a smaller qualifying value may exist on the left
            hi = mid - 1;
        } else {
            lo = mid + 1;         // arr[mid] < x, so everything up to mid is too small
        }
    }
    return ans;
}

Dry run of the floor search on arr = [3, 4, 4, 7, 8, 10], x = 5:

lo hi mid arr[mid] arr[mid] <= 5? action
0 5 2 4 yes ans = 4, lo = 3
3 5 4 8 no hi = 3
3 3 3 7 no hi = 2
3 2     lo > hi return 4

The ceil search on the same input first records 8 at mid = 4, improves to 7 at mid = 3, and then finds nothing smaller that is still >= 5, returning 7.

Complexity. Time O(log n): two independent binary searches. Space O(1).

Notice the mirror symmetry between the two helpers: the floor search is the ceil search with >= flipped to <= and the directions of movement swapped. Getting one right and mirroring it is less error-prone than writing both from scratch.

Intuition. The lower bound lb of x (first index with arr[lb] >= x, or n) already pins down both answers:

One binary search, then two constant-time lookups.

Algorithm.

  1. Compute lb with a half-open binary search: lo = 0, hi = n; while lo < hi, if arr[mid] >= x then hi = mid else lo = mid + 1.
  2. ceil = lb < n ? arr[lb] : -1.
  3. If lb < n and arr[lb] == x, floor = x; else floor = lb > 0 ? arr[lb - 1] : -1.
  4. Return {floor, ceil}.
static int[] optimalLowerBound(int[] arr, int x) {
    int n = arr.length;
    int lb = 0, hi = n;                           // lower bound: first index with arr[idx] >= x, or n
    while (lb < hi) {
        int mid = lb + (hi - lb) / 2;
        if (arr[mid] >= x) hi = mid;
        else lb = mid + 1;
    }
    int ceil = lb < n ? arr[lb] : -1;
    int floor;
    if (lb < n && arr[lb] == x) floor = x;        // x itself is present, so it is its own floor
    else floor = lb > 0 ? arr[lb - 1] : -1;       // every index before lb holds a value < x
    return new int[]{floor, ceil};
}

Complexity. Time O(log n) for one binary search, space O(1).

Edge cases and pitfalls