Page 256 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 14: Searching

14.1 Linear Search Notes

Linear search is a basic form of search. Linear search is the basic searching algorithm, also called
as sequential search. Algorithm searches the element by comparing the each element in the list,
until the desired element found.
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.

Did u know? 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 Θ(n/2) as, in the average case, one-half of the items
in the search space will be examined before a match is found. 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.

14.1.1 Characteristics

The worst case performance scenario for a linear search is that it needs to loop through the entire
collection; either because the item is the last one, or because the item isn’t found. In other words,
if you have N items in your collection, the worst case scenario to find an item is N iterations.
This is known as O(N) using the Big O Notation.

!
Caution The speed of search grows linearly with the number of items within your collection.
Linear searches don’t require the collection to be sorted.

In some cases, you’ll know ahead of time that some items will be disproportionally searched
for. In such situations, frequently requested items can be kept at the start of the collection. This
can result in exceptional performance, regardless of size, for these frequently requested items.
Despite its less than stellar performance, linear searching is extremely common. Many of the
built-in methods that you are familiar with, like ruby’s find_index, or much of jQuery, rely on
linear searches. When you are dealing with a relatively small set of data, it’s often good enough
(and for really small unordered data is can even be faster than alternatives).
Now let us understand linear search with real world example.

Example: As a real world example, pickup the nearest phonebook and open it to the first
page of names. We’re looking to find the first “Smith”. Look at the first name. Is it “Smith”?
Probably not (it’s probably a name that begins with ‘A’). Now look at the next name. Is it
“Smith”? Probably not. Keep looking at the next name until you find “Smith”.

LOVELY PROFESSIONAL UNIVERSITY 249