The simplest way to go through a collection of things and see if any one of them is the one you’re looking for—however inefficient it might be (spoiler alert: very)—is simply to check each element.
An array is a contiguous grouping—that is, next to each other in memory, rather
than all over the place—of some fixed length of elements of the same type.
Suppose for simiplcity (though this can extend beyond this simplest case) that
we just have an array of integers, int[] nums = new int[10];
Here, nums is an array of 10 integers—whole numbers that range from about -2,147,000,000
to +2,147,000,000, where, if no value is specified, the default is 0.
Initially, in a very literal sense, the memory looks like
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
But now, suppose we give those 10 spots some non-zero values:
|
0 |
10 |
37 |
28 |
1000 |
457 |
-29 |
398 |
-2789 |
23798 |
From here, suppose we want to figure out if the number 1000 is in the
collection. We are humans, so we can see the whole collection at once and determine
that 1000 is in the 5th spot, labeled as nums[4] because computers
start counting from 0, so the first position is nums[0]; that nums[0] happens
to have the value 0 inside it, at this point, is pure coincidence.
Computers can’t see the whole collection at once, so the
best we can do on a computer is use a loop to check through each position, as
if we’re opening a series of 10 lockers one by one.
Is it in position 0? No.
Is it in position 1? No.
Is it in position 2? No.
Is it in position 3? No.
Is it in position 4? Yes!—now we can stop because we’ve found it, and either we
report that we found it (as a boolean with the value true),
or we report where we found it (as an int with value 4).
This basic algorithm is called linear search. “Linear” here
may evoke the idea of going down a line of lockers to check them all, but that’s
not where it comes from. It comes from the fact that, checking one at a time, without
assuming anything (i.e., that something is sorted), in the worst case, the
number of failures this algorithm might have before it finds a needle in the haystack
grows linearly (like, for example, the function f(x) = 3x + 2) with the size of
the haystack. If the array is suddenly 20 (double the size), then I might have
to check 20 places. If it shrinks down to 5, then I might have to check 5
places, and so on. (This is as opposed to, for instance, tripling the number of lockers 9x-ing the number of checks. In linear algorithms, tripling the size of the input only triples the number of steps.)
This is a good searching algorithm in that it’s easy to learn, but it isn’t a
very fast one. Soon, we’ll learn a much faster way to find things (leaving
aside the complication of sorting, which we’ll take for granted at this point),
called a binary search. Happy searching!
No comments:
Post a Comment