Search

     
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 $\Theta(n/2)$ as, in the average case, one-half 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.