7.6 Floating-Point Binary Search

The examples in previous sections searched integer domains. Many real-world problems involve continuous values where the answer is not an integer and may not even have an exact representation in memory.

Examples include geometric measurements, physical simulations, financial calculations, optimization problems, and numerical analysis. In these domains, the goal is often to approximate a value within an acceptable error tolerance rather than compute an exact answer.

Binary search extends naturally to continuous search spaces. Instead of searching over discrete positions, the algorithm repeatedly narrows an interval on the real number line until the remaining uncertainty becomes sufficiently small.

This technique is sometimes called binary search on reals, continuous binary search, or bisection search.

Problem

Compute the square root of a positive number.

For example:

√50

The answer is approximately:

7.071067811865...

A brute-force approach might test values incrementally.

7.0
7.01
7.02
7.03
...

This method is inefficient and precision-dependent.

A better approach repeatedly halves the remaining interval.

Solution

Observe the predicate:

x² ≥ 50

Values smaller than the square root produce false.

Values greater than or equal to the square root produce true.

The result forms a monotone boundary.

F F F F F T T T T

Binary search can locate that boundary.

func Sqrt(n float64) float64 {
	lo := 0.0
	hi := n

	if n < 1 {
		hi = 1
	}

	for hi-lo > 1e-9 {
		mid := (lo + hi) / 2

		if mid*mid >= n {
			hi = mid
		} else {
			lo = mid
		}
	}

	return hi
}

Usage:

fmt.Printf("%.9f\n", Sqrt(50))

Output:

7.071067812

The exact digits depend on the stopping tolerance.

Understanding the Search Space

Integer binary search terminates when:

lo == hi

Continuous search spaces contain infinitely many values.

The interval never becomes truly empty.

Instead, the algorithm stops when the interval becomes sufficiently small.

for hi-lo > epsilon

The parameter epsilon determines the desired precision.

Common values include:

1e-3
1e-6
1e-9
1e-12

Smaller values increase accuracy and require more iterations.

Visualizing Convergence

Suppose:

√50

lies between:

7
8

Initial interval:

[0, 50]

After several iterations:

[6.25, 12.5]

Then:

[6.25, 9.375]

Then:

[6.25, 7.8125]

Then:

[7.03125, 7.8125]

Each iteration cuts the uncertainty in half.

Eventually:

[7.071067810, 7.071067812]

The remaining error becomes negligible.

Choosing an Error Tolerance

The stopping criterion directly affects both accuracy and running time.

For example:

Epsilon	Approximate Accuracy
1e-3	Three decimal places
1e-6	Six decimal places
1e-9	Nine decimal places
1e-12	Twelve decimal places

In practice, the required precision depends on the problem domain.

Financial calculations often require strict decimal precision.

Graphics applications may tolerate larger errors.

Scientific simulations frequently require very small tolerances.

Always choose a tolerance appropriate for the application rather than using the smallest possible value.

Fixed Iteration Search

Some systems prefer a fixed number of iterations.

func Sqrt(n float64) float64 {
	lo := 0.0
	hi := n

	if n < 1 {
		hi = 1
	}

	for i := 0; i < 100; i++ {
		mid := (lo + hi) / 2

		if mid*mid >= n {
			hi = mid
		} else {
			lo = mid
		}
	}

	return hi
}

This approach guarantees deterministic execution time.

Since each iteration halves the interval, 100 iterations produce extremely high precision for ordinary applications.

Many competitive programming solutions use fixed iterations because they simplify termination reasoning.

Example: Cube Roots

The technique generalizes immediately.

Suppose you need:

∛100

Define:

x³ ≥ 100

Implementation:

func CubeRoot(n float64) float64 {
	lo := 0.0
	hi := n

	for hi-lo > 1e-9 {
		mid := (lo + hi) / 2

		if mid*mid*mid >= n {
			hi = mid
		} else {
			lo = mid
		}
	}

	return hi
}

No changes are required beyond the predicate.

This illustrates an important pattern: the binary search framework remains constant while the feasibility test changes.

Example: Solving Equations

Suppose you need to solve:

x³ + x - 10 = 0

Define:

f(x) = x³ + x - 10

Values:

f(2) = 0

The root can be located using the sign of the function.

func Solve() float64 {
	lo := 0.0
	hi := 10.0

	for hi-lo > 1e-9 {
		mid := (lo + hi) / 2

		if mid*mid*mid+mid-10 >= 0 {
			hi = mid
		} else {
			lo = mid
		}
	}

	return hi
}

This method is known in numerical analysis as the bisection method.

It is one of the oldest and most reliable root-finding algorithms.

Example: Geometry Optimization

Suppose a circle must cover a set of points.

The objective is:

Find the minimum radius.

Define:

Can radius R cover every point?

Results:

False False False True True True

The radius is a real value.

Binary search repeatedly narrows the feasible interval until the desired precision is achieved.

Many computational geometry problems use this approach.

Monotonicity Requirements

The same monotonicity requirement applies.

Suppose:

f(x) ≥ 0

produces:

F F F T T T T

Binary search works.

However:

F T F T T F

contains multiple transitions.

Binary search assumptions are violated.

Always verify that the predicate changes only once across the search interval.

Numerical Stability

Floating-point arithmetic introduces rounding errors.

For example:

0.1 + 0.2

does not equal:

0.3

exactly.

Comparisons involving floating-point values should therefore use tolerances when appropriate.

Instead of:

a == b

prefer:

math.Abs(a-b) < 1e-9

when the problem permits approximate equality.

This consideration becomes increasingly important in geometry and scientific computing.

Complexity Analysis

Suppose the initial interval length is:

and the desired precision is:

ε

Each iteration halves the interval.

After k iterations:

R / 2ᵏ

The search stops when:

R / 2ᵏ ≤ ε

Therefore:

k = O(log(R / ε))

Time complexity:

O(log(R / ε))

Space complexity:

O(1)

This logarithmic dependence on precision makes binary search extremely efficient for continuous optimization problems.

Common Mistakes

One common error is using:

for lo < hi

with floating-point values. Due to rounding behavior, the interval may never collapse exactly.

Always terminate using a tolerance or a fixed iteration count.

Another mistake is selecting an interval that does not contain the solution. Binary search can only locate a boundary that already lies inside the search range.

A third mistake occurs when the predicate is not monotone. Continuous domains do not eliminate the monotonicity requirement.

Finally, some implementations use unnecessarily small tolerances such as:

1e-18

without considering floating-point precision limits. Beyond a certain point, additional iterations provide no meaningful improvement.

Takeaway

Floating-point binary search extends the boundary-search concept from discrete values to continuous domains. By repeatedly halving an interval and evaluating a monotone predicate, the algorithm can efficiently approximate roots, geometric measurements, optimization parameters, and physical quantities. The core framework remains identical to integer binary search. The primary differences are the use of an error tolerance and the interpretation of the search space as a continuum rather than a finite collection of positions.