Linear Search, as the name implies is a searching algorithm which obtains its result by traversing a list of data items in a linear fashion. It will start at the beginning of a list, and mosey on through until the desired element is found, or in some cases is not found.

**Analysis of Linear Search**

Linear
Search, as the name implies is a searching algorithm which obtains its result
by traversing a list of data items in a linear fashion. It will start at the
beginning of a list, and mosey on through until the desired element is found,
or in some cases is not found. The aspect of Linear Search which makes it
inefficient in this respect is that if the element is not in the list it will
have to go through the entire list. As you can imagine this can be quite
cumbersome for lists of very large magnitude, keep this in mind as you
contemplate how and where to implement this algorithm. Of course conversely the
best case for this would be that the element one is searching for is the first
element of the list, this will be elaborated more so in the â€•Analysis &
Conclusionâ€– section
of this tutorial.

**Linear Search Steps:**

*Step 1 - Does the item match the
value Iâ€™m looking for?*

*Step 2 - If it does match return,
youâ€™ve found your item! Step 3 - If it does not match advance and repeat the
process.*

*Step 4 - Reached the end of the
list and still no value found? Well obviously the item is not in the list!
Return -1 to signify you have not found your value.*

As
always, visual representations are a bit more clear and concise so let me present
one for you now. Imagine you have a random assortment of integers for this
list:

Legend:

-The key
is blue

-The
current item is green. -Checked items are red

Ok so
here is our number set, my lucky number happens to be 7 so letâ€˜s put this value
as the key, or the value in which we hope Linear Search can find. Notice the
indexes of the array above each of the elements, meaning this has a size or
length of 5. I digress let us look at the first term at position 0. The value
held here 3, which is not equal to 7. We move on.

--0 1 2 3
4 5 [ 3 2 5 1 7 0 ]

So we hit
position 0, on to position 1. The value 2 is held here. Hmm still not equal to
7. We march on.

--0 1 2 3
4 5 [ 3 2 5 1 7 0 ]

Position
2 is next on the list, and sadly holds a 5, still not the number weâ€˜re looking
for. Again we move up one.

--0 1 2 3
4 5 [ 3 2 5 1 7 0 ]

Now at
index 3 we have value 1. Nice try but no cigar letâ€˜s move forward yet again.
--0 1 2 3 4 5 [ 3 2 5 1 7 0 ]

Ah Ha!
Position 4 is the one that has been harboring 7, we return the position in the
array which holds 7 and exit.

--0 1 2 3
4 5 [ 3 2 5 1 7 0 ]

As you
can tell, the algorithm may work find for sets of small data but for incredibly
large data sets I donâ€˜t think I have to convince you any further that this would
just be down right inefficient to use for exceeding large sets. Again keep in
mind that Linear Search has its place and it is not meant to be perfect but to
mold to your situation that requires a search.

Also note
that if we were looking for lets say 4 in our list above (4 is not in the set)
we would traverse through the entire list and exit empty handed. I intend to do
a tutorial on Binary Search which will give a much better solution to what we
have here however it requires a special case.

*//linearSearch Function*

*int linearSearch(int data[], int
length, int val) {*

*for (int
i = 0; i <= length; i++) { if (val == data[i]) {*

*return i;
}//end if*

*}//end for*

*return
-1; //Value was not in the list }//end linearSearch Function*

**Analysis & Conclusion**

As we have
seen throughout this tutorial that Linear Search is certainly not the absolute
best method for searching but do not let this taint your view on the algorithm
itself. People are always attempting to better versions of current algorithms
in an effort to make existing ones more efficient. Not to mention that Linear
Search as shown has its place and at the very least is a great beginnerâ€˜s
introduction into the world of searching algorithms. With this is mind we
progress to the asymptotic analysis of the Linear Search:

**Worst Case:**

The worse
case for Linear Search is achieved if the element to be found is not in the
list at all. This would entail the algorithm to traverse the entire list and
return nothing. Thus the worst case running time is:

O(N).

**Average Case:**

The
average case is in short revealed by insinuating that the average element would
be somewhere in the middle of the list or N/2. This does not change since we
are dividing by a constant factor here, so again the average case would be:

O(N).

**Best Case:**

The best
case can be a reached if the element to be found is the first one in the list.
This would not have to do any traversing spare the first one giving this a
constant time complexity or:

O(1).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Analysis and Design of Algorithm : Analysis of Linear Search |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.