Game Development Reference
In-Depth Information
For example, if guessing a number between 1 and 100, we want to start at 50. If
we are told that the number is
higher
than 50, we would guess 75. If we are then told
“lower,� our next guess would be 62. On each turn, we divide the remaining range
in half, thereby maximizing the possibility that it is on either side of an incorrect
guess. Compare this to the brute force method we listed above. That approach is
analogous to guessing the lowest possible number on each iteration and being told
“higher� until, one step at a time, we reach the target. Using that method, the max-
imum number of guesses is equal to the number of possibilities. If we are guessing
a number between 1 and 100, we
could
end up guessing 100 times to determine the
target (if the number was 100).
On the other hand, a binary search performs in O(log
2
n
) time, where
n
is the
number of elements. In the classic “guess the number between 1 and 100� game, we
would need a maximum of seven guesses to determine the target. If we were to
expand the game from 1 to
200
instead, we would only need one additional guess
(eight total). Guessing a number between 1 and 400 requires only nine guesses.
Between 1 and 800? Only 10 guesses. It becomes apparent very quickly that a binary
search is an efficient way of finding data.
The major requirement for a binary search is that the data we are searching is
stored in a sorted fashion. If it was not, then we could not determine “higher� or
“lower�… only whether or not we were correct. Imagine asking someone to guess
the name of an animal. When they did so, we could tell them “correct� or “incor-
rect.� The answer of “incorrect� doesn't help them determine what direction they
should take on their subsequent guess, however. If we told them that the animal
they were attempting to guess was, for example, “earlier in the alphabet� or “heav-
ier� than the one they just guessed, we would be giving them a direction in which
to head. With that information, they could use a similar “divide and conquer�
strategy to close in on the correct answer.
In the example we are working with, the values of
x
are stored in the vector in
sorted order from lowest to highest. That way, when we test the value of
x
at a par-
ticular array index (
i
), we can determine if we are higher or lower (assuming we are
not correct) and move in the proper direction from that point. Therefore, a binary
search is a valid approach.
The code for a binary search isn't difficult to write. We need only keep track of
the highest and lowest possible bounds at any given time. Then, we calculate the
midpoint between them as our guess and check to see if our guess was correct, high,
or low. The following searches our vector for the proper value of
x
to return the
corresponding
y
.
double CLinearFunction::GetY_BinarySearch( int x )
{
