Game Development Reference
In-Depth Information
Stepping through the function from the beginning, we first determine the
number of elements in the vector. We set our initial bounds for the search at 0 and
one less than the number of elements. (Vectors are 0-referenced, so
n
elements
means the last index is
n
- 1.) In the
while
loop, we set our guess index (
i
) to the
halfway point between whatever the current high and low are. We then check the
value of
x
held at the point in the vector referenced by
i
. If it matches the
x
we are
looking for, we are finished and return the corresponding
y
. If not, we then deter-
mine whether our guess was too high or too low and change our upper or lower
bounds accordingly. We then repeat the
while
loop to make a new guess until such
time as we guess correctly.
Notice that, as written, the while loop should not end because we never change
the value of
found
. If we wanted to, we could write in various error traps to avoid
such things as infinite loops. I left them out here for clarity of code.
The binary search method has given us a few improvements over the prior
methods. As we discussed above, the binary search method is significantly faster
than the brute force method—especially when we work with larger data sets.
Additionally, unlike the offset method, we no longer have to keep track of the rela-
tionship between the vector index and the data contained in the vector. This last
part is significant for one last reason: by design, the vector indices necessarily have
to increment by one—we may not want to hold our data to the same requirement.
In the previous examples, we were matching up a single
x
with a single
y
. That is,
any given input generated an output. However, if we think back to the original (and
delightfully simple) dentist example, we encounter a different requirement.
We can think of the “ball into bucket� metaphor as having two different types
of input. First, we think of the ball in terms of dropping into one of five different
segments of the range. In a way, we have recast this as being
five
buckets rather than
two. In this case, buckets 1 through 4 mean that the dentist recommends sugarless
gum and bucket 5 indicates that he doesn't.
If we were to create our dentist example using the 1-to-1 methods outlined
above, we would be inclined to create a five-unit vector—the first four of which
were mapped to one output (“sugarless�) and the fifth mapped to the other
(“tooth-rotting�). However, it does seem rather inefficient to have four slots in our
vector all pointing to the same outcome.
On the other hand, we can also think of the ball dropping into one of only
two
buckets—the two buckets representing our two choices. It just so happens, of
