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.

Practice

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

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 the floor definition

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

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches this definition exactly, while 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 ≤ number, pick greatest such element [OK]

Common Mistakes:

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

2. Which Go code snippet correctly declares a function to find the floor in a sorted array?

easy

A. func floor(arr int[], x int) int { /* code */ }

B. func floor(arr []int, x int) int { /* code */ }

C. function floor(arr []int, x int) int { /* code */ }

D. func floor(arr []int, x int) void { /* code */ }

Solution

1. Step 1: Check Go function syntax

   In Go, functions are declared with func, parameter types follow names, and return type is after parameters.

2. Step 2: Validate each option

   func floor(arr []int, x int) int { /* code */ } uses correct Go syntax: func floor(arr []int, x int) int. func floor(arr int[], x int) int { /* code */ } uses incorrect array syntax, C uses wrong keyword, D has wrong return type.

3. Final Answer:

   func floor(arr []int, x int) int { /* code */ } -> Option B

4. Quick Check:

   Go func syntax = func floor(arr []int, x int) int { /* code */ } [OK]

Hint: Go arrays use []type, func keyword, return type after params [OK]

Common Mistakes:

• Using 'function' keyword instead of 'func'
• Incorrect array type syntax
• Wrong return type declaration

3. What is the output of the following Go code snippet?

arr := []int{1, 3, 5, 7, 9}
x := 6
floor := -1
for _, val := range arr {
    if val <= x {
        floor = val
    } else {
        break
    }
}
fmt.Println(floor)

medium

A. 5

B. 6

C. 7

D. -1

Solution

1. Step 1: Trace the loop over array elements

   The loop checks each element: 1 ≤ 6 (floor=1), 3 ≤ 6 (floor=3), 5 ≤ 6 (floor=5), 7 ≤ 6? No, break loop.

2. Step 2: Determine final floor value

   Last floor assigned is 5, so printed output is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Floor of 6 in arr = 5 [OK]

Hint: Floor is last element ≤ x before break [OK]

Common Mistakes:

• Assuming floor equals x if not present
• Not breaking loop early
• Confusing floor with ceil

4. Identify the bug in this Go code to find the ceil of x in a sorted array arr:

func ceil(arr []int, x int) int {
    ceil := -1
    for _, val := range arr {
        if val >= x {
            ceil = val
        }
    }
    return ceil
}

medium

A. It uses wrong comparison operator

B. It initializes ceil with -1 incorrectly

C. It returns ceil before loop ends

D. It does not break after finding first valid ceil

Solution

1. Step 1: Analyze loop behavior for ceil

   The loop updates ceil whenever val ≥ x, but does not stop after first valid ceil, so it ends with the last such value, which may not be the smallest ceil.

2. Step 2: Identify correct fix

   To find the smallest ceil, the loop should break immediately after first val ≥ x is found.

3. Final Answer:

   It does not break after finding first valid ceil -> Option D

4. Quick Check:

   Ceil needs first ≥ x, break loop [OK]

Hint: Break loop on first val ≥ x for correct ceil [OK]

Common Mistakes:

• Not breaking loop early
• Confusing ceil with floor logic
• Incorrect initialization of ceil

5. Given a sorted array arr := []int{2, 4, 6, 8, 10} and a number x = 5, write a Go function that returns both floor and ceil of x. What is the correct output of floor and ceil?

hard

A. Floor: -1, Ceil: -1

B. Floor: 6, Ceil: 4

C. Floor: 4, Ceil: 6

D. Floor: 5, Ceil: 5

Solution

1. Step 1: Find floor of 5 in arr

   Floor is greatest element ≤ 5. Elements ≤ 5 are 2 and 4, greatest is 4.

2. Step 2: Find ceil of 5 in arr

   Ceil is smallest element ≥ 5. Elements ≥ 5 are 6, 8, 10, smallest is 6.

3. Final Answer:

   Floor: 4, Ceil: 6 -> Option C

4. Quick Check:

   Floor ≤ x ≤ Ceil = 4 ≤ 5 ≤ 6 [OK]

Hint: Floor ≤ x ≤ Ceil in sorted array [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals x if not present
• Returning -1 when valid floor or ceil exists