Page 1 of 1

Linear Search: Everything You Wanted to Know A description, implementation, analysis, and basic information about L Rate Topic: ****- 1 Votes

#1 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 14
  • View blog
  • Posts: 548
  • Joined: 17-October 07

Posted 11 July 2008 - 11:25 AM

Introduction:


This tutorial is based on the searching algorithm ďLinear SearchĒ, the most stripped down and easy to understand searching algorithm. Students who initially are getting started in this aspect find this to be one of the more logical ways of searching, however far from efficient. Never the less this is a staple searching algorithm that is still used and taught everywhere for various reasons. Linear Search still has a vital role in actual implementations, it is very easy to code and sometimes a Linear Search is all that is necessary for particular situations and avoidance of headaches caused by writing more complex code when in reality the situation may not call for it.

It is such that learning this method is an essential stepping stone into more advanced searching algorithms. You will develop an appreciation of more complex algorithms as you progress to them by learning what makes them more efficient. Furthermore to understand and gain that appreciation you must build a strong foundation that will allow you to do so. With that said let me introduce you to the world that is Linear Search.

:blink: What is 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.

The Algorithm:

The algorithm for this one is pretty straightforward as we shall see. Letís take a look at how itís done:

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.

The Code:


The following code is a basic Linear Search routine, it takes all of what we have talked about up until this point and puts it into code. As you can see it is very easy to follow.

//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).

Is This A Good Question/Topic? 0
  • +

Replies To: Linear Search: Everything You Wanted to Know

#2 Adriel16  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 61
  • Joined: 21-May 13

Posted 09 November 2017 - 04:28 PM

In this example I see that you did not place a size in declaration of the array,
int data[]
. My question, is how would I go about writing your exact example without using a function. I ask because I want to learn without using a function first then move on to implementing searches in functions and in my code I've declared the array,
int data[]
but received an error that I did not specify a size. Thank you in advance! Also, well explained tutorial!

This post has been edited by Adriel16: 09 November 2017 - 04:28 PM

Was This Post Helpful? 0
  • +
  • -

#3 Adriel16  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 61
  • Joined: 21-May 13

Posted 09 November 2017 - 07:16 PM

Never mind I got it working but the comparison had to be different than what you wrote in order for the program to run.
Was This Post Helpful? 0
  • +
  • -

#4 ndc85430  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 598
  • View blog
  • Posts: 2,498
  • Joined: 13-June 14

Posted 10 November 2017 - 09:02 AM

When you pass an array to a function, you typically don't give a size there - remember that arrays in C/C++ are basically pointers. You pass the size as another parameter (i.e. length in the example above).

Also, I'm not sure in what way your comparison would have to be different. As soon as you find an item that matches (i.e. is equal to) what you're looking for, you can stop iterating.

Of course, linear search is going to be really slow if N is large. If the array is sorted, then a binary search will be more efficient. The worst case time complexity for binary search is O(log N), where the logarithm is to base 2. You may want to go and investigate how binary search works.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1