Page 257 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The above is an example of a sequential search. You started at the beginning of a sequence and
went through each item one by one, in the order they existed in the list, until you found the item
you were looking for.
Now we’ll look at this as related to computer science. Instead of a phonebook, we have an array.
Although the array can hold data elements of any type, for the simplicity of an example we’ll
just use an array of integers, like the following:

Let’s search for the number 3. We start at the beginning and check the first element in the array.

As we can see, it is not 3, move to the next element.

Again move to the next element, as it is not 3.

As we can see in the figure below, the next value is number 3..

Source: http://www.sparknotes.com/cs/searching/linearsearch/section1.rhtml
Now you understand the idea of linear searching; we go through each element, in order, until
we find the correct value.

Sequential search has some advantages over other searches. Most importantly, it doesn’t require
the array to be sorted, since every array element is examined. In addition, linear search is quite
easy to implement, as evidenced by the relative simplicity of the code above. The disadvantage
of sequential search is efficiency. Since this approach examines every element in the list, it does
work for every element. Therefore, linear search is O(n), relatively inefficient, as sorting
algorithms go.

Task Analyze the real world examples of linear search.

14.1.2 A Function to Implement Linear Search

Let’s apply a linear search algorithm and write a function to carry it out. Our function will take
three arguments: the array to search, the number of elements in the array, and a value to search
for. The function will return the index into the array that the value was found at, or –1 if the value
wasn’t found.

250 LOVELY PROFESSIONAL UNIVERSITY