Floor and Ceiling Functions: The Rounding Rules Behind Binary Search

You've seen floor and ceiling before. Probably in a precalculus class where the examples were like floor(3.7) = 3 and everyone moved on within thirty seconds. Then you sat down to implement binary search, wrote mid = (lo + hi) / 2, and your loop ran forever. That's floor doing something very specific, and understanding it is the difference between correct binary search and a very patient program that never actually terminates.

Floor Rounds Toward Negative Infinity. Yes, Even for Negative Numbers.

Floor of x is the largest integer that is less than or equal to x.

floor(2.9) is 2. floor(3.0) is 3. floor(-2.1) is -3.

That last one is where people get tripped up. Your brain says "round toward zero, so -2." Floor doesn't care about zero. Floor rounds toward negative infinity, which for negative numbers means going away from zero. The mental model: floor always goes further down the number line.

import math

math.floor(2.9)   # 2
math.floor(3.0)   # 3
math.floor(-2.1)  # -3 (not -2!)
math.floor(-3.0)  # -3

Two things to pin down: for any non-integer x, floor and ceiling differ by exactly 1. For any integer x, floor(x) equals ceil(x) equals x itself.

Ceiling Is Just Floor's Contrarian Twin

Ceiling of x is the smallest integer that is greater than or equal to x.

ceil(2.1) is 3. ceil(3.0) is 3. ceil(-2.9) is -2.

Ceiling rounds toward positive infinity. It always goes up the number line.

import math

math.ceil(2.1)   # 3
math.ceil(3.0)   # 3
math.ceil(-2.9)  # -2
math.ceil(-3.0)  # -3

The One Arithmetic Trick You'll Actually Use

In interviews you rarely import a math library. You compute floor and ceiling with integer arithmetic, and one formula appears constantly.

Integer division in most languages truncates toward zero. For positive numbers that's the same as floor. For negative numbers it's not.

7 // 2    # 3  (floor, toward negative infinity in Python)
-7 // 2   # -4 (still floor in Python)

Java and C++ truncate toward zero, which is different:

int a = 7 / 2;   // 3 (truncation = floor for positives)
int b = -7 / 2;  // -3 (truncation, NOT floor: floor would be -4)

Python's // is true floor division. Java's / on integers truncates toward zero, which acts like floor for positive numbers and like ceiling for negative ones. Most interview problems involve non-negative indices and sizes, so this rarely bites you. But it can.

For ceiling with positive integers, the standard trick is:

ceil(n / k)  ==  (n + k - 1) // k

If you have 10 items and need groups of 3, you need (10 + 2) // 3 = 4 groups. No import math, no float precision issues. This formula appears in dozens of interval problems, bucket problems, and binary search check functions.

Why it works: adding k - 1 before dividing pushes any non-multiple into the next bucket. Multiples of k already sit exactly on a boundary, so the extra k - 1 doesn't tip them over.

Pick the Wrong One and Your Binary Search Loops Forever

Every binary search midpoint calculation is choosing between floor and ceiling:

# Floor mid (biased toward lo)
mid = lo + (hi - lo) // 2

# Ceiling mid (biased toward hi)
mid = lo + (hi - lo + 1) // 2

For lo = 0 and hi = 6: floor mid is 3, ceiling mid is 3 (same). For lo = 0 and hi = 7: floor mid is 3, ceiling mid is 4.

This choice creates an infinite loop if you get it wrong. Say lo = 1 and hi = 2. With floor mid, mid = 1. If your update is lo = mid, you set lo = 1 and nothing moves. The loop spins forever. You sit there convinced your logic is correct. Your interviewer watches the cursor blink. Your binary search is perfectly implementing a very reliable "do nothing forever" machine.

The rule: if your update is lo = mid, use ceiling mid. If your update is hi = mid, use floor mid. Each update shrinks the search space by at least one, guaranteeing termination. This is the actual hard part of binary search. Not the algorithm itself. Just this.

See binary search algorithm for a full treatment of the invariant.

Your Heap Parent Formula Is a Floor Calculation

A 0-indexed array heap has this structure:

Left child of node i: 2 * i + 1
Right child of node i: 2 * i + 2
Parent of node i: (i - 1) // 2

That parent calculation floors the result. Nodes 1 and 2 are both children of node 0: (1 - 1) // 2 = 0 and (2 - 1) // 2 = 0. Nodes 3 and 4 are children of node 1: (3 - 1) // 2 = 1 and (4 - 1) // 2 = 1. Every pair of siblings maps to the same parent via floor division.

A 1-indexed heap uses i // 2 for the parent. Same principle, cleaner indexing. See heap data structure for how the array layout connects to the tree shape.

The Floor Hidden Inside O(log n)

A perfect binary tree with n nodes has height floor(log2(n)). Binary search on a sorted array of n elements takes at most floor(log2(n)) + 1 comparisons. Both follow from the same counting argument: each level of a binary tree doubles the node count, so the number of levels is the floor of the base-2 logarithm.

When you say binary search is O(log n), what you're really saying is it runs for floor(log2(n)) + 1 iterations at most. The floor is built into the bound. See logarithmic time complexity for the full derivation.

This Overflow Bug Lived in Java's Standard Library for Nearly a Decade

Here is the most common floor mistake in interview code:

// Dangerous: lo + hi can overflow Integer.MAX_VALUE
int mid = (lo + hi) / 2;

// Safe: computes the same floor, avoids overflow
int mid = lo + (hi - lo) / 2;

Both expressions compute floor((lo + hi) / 2). The second one subtracts first so the intermediate value stays bounded. This was an actual bug in Java's standard library Arrays.binarySearch, shipped in JDK 1.2, not fixed until JDK 6. Nearly a decade. In the standard library. The canonical Java binary search implementation had the textbook binary search bug the whole time.

If you write (lo + hi) / 2 in an interview, mention the overflow risk. Even if constraints make overflow impossible for that problem, naming the issue signals that you know what you're doing. See integer overflow in coding interviews for more on where this catches engineers.

All These Languages Handle It Differently

Language	Floor	Ceiling	Integer division
Python 3	`math.floor(x)` or `x // 1`	`math.ceil(x)`	`//` is true floor
Python 2	`math.floor(x)` (returns float)	`math.ceil(x)`	`//` is true floor
JavaScript	`Math.floor(x)`	`Math.ceil(x)`	`Math.trunc(x)` truncates
TypeScript	`Math.floor(x)`	`Math.ceil(x)`	Same as JS
Java	`Math.floor(x)`	`Math.ceil(x)`	`/` truncates toward zero
C++	`std::floor(x)`	`std::ceil(x)`	`/` truncates toward zero
C	`floor(x)`	`ceil(x)`	`/` truncates toward zero
Go	`math.Floor(x)`	`math.Ceil(x)`	`/` truncates toward zero
Rust	`x.floor()`	`x.ceil()`	`/` truncates toward zero
Swift	`x.rounded(.down)`	`x.rounded(.up)`	`/` truncates toward zero
Kotlin	`floor(x)`	`ceil(x)`	`/` truncates toward zero
C#	`Math.Floor(x)`	`Math.Ceiling(x)`	`/` truncates toward zero
Ruby	`x.floor`	`x.ceil`	`/` truncates (or `x.fdiv(y).ceil`)
PHP	`floor($x)`	`ceil($x)`	`/` returns float; cast with `(int)`

Python is the only major language where // is true floor division, not truncation. Kotlin and Swift have idiomatic single-method calls on numeric types rather than a math module.

For the ceiling-without-floats trick, the formula (n + k - 1) / k works in every language for positive n and k, using that language's integer division operator.

Key Rules

Floor rounds toward negative infinity. Ceiling rounds toward positive infinity. For integers, both equal the input.
Python's // is true floor division. Java, C++, Go, Rust, and most other languages truncate toward zero, which matches floor only for non-negative numbers.
Ceiling without floats: (n + k - 1) // k for positive integers n and k.
Binary search mid: use floor mid when your update is hi = mid. Use ceiling mid when your update is lo = mid. Mix them up and you get an infinite loop.
Heap parent: (i - 1) // 2 for 0-indexed. Floor division maps every pair of siblings to one parent.
Integer overflow in (lo + hi) / 2 is real. Write lo + (hi - lo) / 2 instead.

The best way to internalize when your midpoint needs floor versus ceiling is to talk through it out loud while you code. SpaceComplexity evaluates exactly that kind of spoken reasoning, which is where most binary search bugs actually surface in real interviews.