Game Development Reference
In-Depth Information
The drawback of this method is that it doesn't scale well to large data sets. The
search time scales linearly with the number of members that we add to our vector.
That is, if we have 41 members (as in our example above), we are going to average
searching 20.5 members to find our match. If we have 1,000 members in the data
set, we are going to be searching 500 of them on average… and as many as all 1,000
in the worst-case scenario.
Offset
Certainly, if we know the offset from the vector index to the lowest
x
value, we
could leverage that to find the proper container. For example, we know that our
lowest number in this exercise was 125. The lowest index in a vector is 0. Therefore,
to find the container that corresponds to any given
x
value, we subtract 125 from
the
x
value we actually want to look up. If we wanted to find
y
when
x
= 130, we
could find it this way:
y = mvElementVector[x - 125].y;
If
x
= 130, the above statement would yield the equivalent of:
y = mvElementVector[5].y;
This method is problematic in that we have to keep track of the offset in a sep-
arate location—either hard-coded as a constant such as above or held separately in
a variable. Either way, if we change the range of our
x
values, we have to remember
to change this offset. We could avoid this by setting the offset to the
x
value of the
first element in the first place:
Offset = mvElementVector[0].x;
y = mvElementVector[x - Offset].y;
The above method works in the scenario that we have set out. It also is signifi-
cantly faster than the brute force method. There is a better way, however—one that
allows us to do some nifty tricks down the road.
Binary Search
For those who aren't familiar with the
binary search
technique, it is, in essence, a
game of “guess the number.� The three possible outcomes are “higher,� “lower,�
and “got it!� If you have every played this game, you realize that the most efficient
way of guessing the number is to take a “divide and conquer� approach.
