Floor and Ceil in Sorted Array in DSA Go

Mental Model

Floor is the biggest number smaller or equal to target; ceil is the smallest number bigger or equal to target in a sorted list.

Analogy: Imagine standing on a number line with sorted stones; floor is the closest stone behind or at your feet, ceil is the closest stone ahead or at your feet.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: 5 (closest ≤ 6)
Ceil: 7 (closest ≥ 6)

Dry Run Walkthrough

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

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

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

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

Why: We use binary search to quickly find floor and ceil in sorted array

Step 2: Calculate mid=2, array[mid]=5, which is less than target 6

[1, 3, 5, 7, 9], low=0, high=4, mid=2 (value=5)

Why: Since 5 < 6, floor candidate updated to 5, search right half for closer floor or ceil

Step 3: Update low=mid+1=3, high=4, calculate mid=3, array[mid]=7

[1, 3, 5, 7, 9], low=3, high=4, mid=3 (value=7)

Why: 7 > 6, so ceil candidate updated to 7, search left half for closer ceil

Step 4: Update high=mid-1=2, now low=3 > high=2, stop search

[1, 3, 5, 7, 9], low=3, high=2 (stop)

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

Result:

Floor: 5
Ceil: 7

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func floorAndCeil(arr []int, target int) (int, int) {
	floor, ceil := -1, -1
	low, high := 0, len(arr)-1
	for low <= high {
		mid := low + (high-low)/2
		if arr[mid] == target {
			return arr[mid], arr[mid] // exact match is both floor and ceil
		} else if arr[mid] < target {
			floor = arr[mid] // update floor candidate
			low = mid + 1 // search right half
		} else {
			ceil = arr[mid] // update ceil candidate
			high = mid - 1 // search left half
		}
	}
	return floor, ceil
}

func main() {
	arr := []int{1, 3, 5, 7, 9}
	target := 6
	floor, ceil := floorAndCeil(arr, target)
	fmt.Printf("Floor: %d\nCeil: %d\n", floor, ceil)
}

for low <= high {

loop to narrow search range until low passes high

mid := low + (high-low)/2

calculate middle index to check

if arr[mid] == target { return arr[mid], arr[mid] }

exact match means floor and ceil are the same

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

update floor candidate and search right half

else { ceil = arr[mid]; high = mid - 1 }

update ceil candidate and search left half

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: Linear search would be O(n) by checking each element; binary search is faster for sorted arrays

Edge Cases

target smaller than all elements

floor remains -1 (no smaller or equal), ceil is first element

DSA Go

floor, ceil := -1, -1

target larger than all elements

floor is last element, ceil remains -1 (no larger or equal)

DSA Go

floor, ceil := -1, -1

target exactly matches an element

floor and ceil both equal target element

DSA Go

if arr[mid] == target { return arr[mid], arr[mid] }

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving search boundaries
Fix: Update floor when arr[mid] < target and update ceil when arr[mid] > target before changing low or high

Summary

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

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

The key is to use binary search and update floor and ceil candidates while narrowing the search.