The most simplistic numerical techniques are based on bracketing the
problem. If we have a function of one variable, if we can determine
that a solution to our problem lies on a particular interval [*a*, *b*],
it seems reasonable that if we can select a point on that interval,
say *c*, then if we can determine whether or not the solution lies in
[*a*, *c*] or [*c*, *b*], then we have restricted the
domain on which we know the solution lies. In that case, we can try again:
shrink the new interval and get a tighter bound on the solution.

# Example

Humans use bracketing quite often. Consider a search through a dictionary. It
is known that the first page of the standard English dictionary contains words starting with A,
and the last contains words starting with Z. Any word you are looking for is bounded
by these two points. By opening the dictionary at a page, it is easy to determine whether
or not the word you are looking for lies before, on, or after that page. In this
case, you have shrunk the number of pages you are searching: assuming we have not found
the page containing the word, we are assured that the word lies either before or after
the page we are currently inspecting. Next, we repeat this process on that portion of
the dictionary in which the word is known to lie.

This may seem to be a very fast algorithm (for those who have studies run-times, you
will know that such an algorithm is O(log(*n*))), however, unfortunately, it is
an exceptionally slow numerical technique, as we will see.

# Problems

Bracketing does not work very well in higher dimensions. For example,
a system of *n* equations and *n* unknowns requires 2^{n}
points. However, it is very useful, still, when it is known that the
function is exceptionally *wild*, that is, it is a low-dimensional
problem, but it is known that the derivative and second-derivatives
are very large on the interval of interest. In this case, using
either interpolation or Taylor series will almost certainly result in non-convergent
iterations.

# Question

What properties of a dictionary or phone book do you use to speed up a bracketing
search?