The Basic Searching Algorithm: Linear Search

Written by Raza on. Posted in C++

We search for different sort of things in our daily life. This search process is so common and typical that we do not realize how actually search is being performed. And that how the required key is brought out from the depth of information of the massive databases. In computer science, there are many methods for searching a key inside a list. Just like various sorting techniques, there are many searching algorithms as well. A basic and primitive searching method is to look at every element of the list and match the required information. This is known as Linear Search. I shall explain to you what linear search in essence is. 


Basic Principle of Linear Search:

Linear search is named linear because it searches for the required piece of information inside the list in a straight line fashion. The required piece of information is known as key. It looks at each and every element of the list and checks whether key is found or not. If it is found, then it tells us that it has been found. Same is the case when it is not found.

The problem with linear search is its running time. It has to look at every single element of the list from the start till the end. Imagine you have a list of 2000 items and the required key is located at the last element of the list. You would have to traverse throughout 1999 elements till you reach the key. So it is pretty inefficient method of searching. For smaller lists, though it can be employed with good results.


Source Code for Linear Search:

While writing the code for linear search, make sure that you end the list when your key is found. Also make sure that if it is online casino not found and the size of the list reaches, terminate the searching process. Here is a basic source code for linear search algorithm.


<p>bool linear_search (int arr[], const int size, const int key)<br />
{<br />
.  bool found = false ;<br />
.  for (int i = 0 ; i &lt; size ; i)<br />
.  {<br />
.   if (key == arr[i])<br />
.   {<br />
.    found = true ;<br />
.    break ;<br />
.   }<br />
.  }<br />
.  return found ;<br />
<p>.<br />
int main ()<br />
{<br />
.  int arr [10] = {1, 2, 7, 5, 4, 10, 11, 20, 50, 3} ;<br />
.  int key = 5 ;<br />
.  bool found = linear_search (arr, 10, key) ;<br />
.  cout &lt;&lt; boolalpha &lt;&lt; found ;<br />


Next time, I would be exploring binary search which is a very good technique to search for a key in the list. Till then, Good Bye!

Tags: , , ,