0.2.1 Linear Search
This method of searching for data in an array is straightforward and
easy to understand. To find a given item, begin your search at the
start of the data collection and continue to look until you have
either found the target or exhausted the search space. Clearly to
employ this method you must first know where the data collection
begins and the size of the area to search. Alternatively, a unique
value could be used to signify the end of the search space. This
method of searching is most often used on an array data structure
whose upper and lower bounds are known.
The complexity of this type of search is O(N) because, in the worst
case all items in the search space will be examined. This type of
search is
as, in the average case, onehalf of the items
in the search space will be examined before a match is found. As we
will see in later sections, there are many algorithms for improving
search time that can be used in place of a linear search. For
instance, the binary search
algorithm operates much more efficiently than a linear search but
requires that the data being searched be in sorted order. Because
there are faster ways of searching a memory space, the linear search
is sometimes referred to as a brute force
search.
