Linear Search Algorithm Explained: Definition and Implementation
☰Fullscreen
Table of Content:
Linear search is a sequential searching algorithm where we start from one end and check every element of the list until the desired element is found. It is the simplest searching algorithm.
Algorithm
Linear Search ( Array A, Value x) Step 1: Set i to 1 Step 2: if i > n then go to step 7 Step 3: if A[i] = x then go to step 6 Step 4: Set i to i + 1 Step 5: Go to Step 2 Step 6: Print Element x Found at index i and go to step 8 Step 7: Print element not found Step 8: Exit
Pseudocode
procedure linear_search (list, value) for each item in the list if match item == value return the item's location end if end for end procedure
Linear search in C programming: The following code implements linear search (Searching algorithm) which is used to find whether a given number is present in an array and if it is present then at what location it occurs. It is also known as sequential search. It is straightforward and works as follows: We keep on comparing each element with the element to search until it is found or the list ends. Linear search in C language for multiple occurrences and using function.
Linear search C program
<span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> array</span><span class="pun">[</span><span class="lit">100</span><span class="pun">],</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter the number of elements in array\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">n</span><span class="pun">);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter %d integer(s)\n"</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter a number to search\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> search</span><span class="pun">)</span><span class="pln"> </span><span class="com">/* If required element is found */</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d is present at location %d.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">+</span><span class="lit">1</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">break</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">==</span><span class="pln"> n</span><span class="pun">)</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d isn't present in the array.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span>
Output:
Enter the number of elements in array 10 Enter 10 integer(s) 9 6 8 6 2 2 7 8 66 23 Enter a number to search 23 23 is present at location 10. Press any key to continue . . .
Linear search for multiple occurrences
In the code below we will print all the locations at which required element is found and also the number of times it occur in the list.
<span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> array</span><span class="pun">[</span><span class="lit">100</span><span class="pun">],</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> count </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter the number of elements in array\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">n</span><span class="pun">);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter %d numbers\n"</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter the number to search\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> search</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d is present at location %d.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">+</span><span class="lit">1</span><span class="pun">);</span><span class="pln"> count</span><span class="pun">++;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">count </span><span class="pun">==</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d isn't present in the array.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d is present %d times in the array.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> count</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span>
Output
Enter the number of elements in array 10 Enter 10 numbers 9 8 7 6 5 3 3 2 1 3 Enter the number to search 3 3 is present at location 6. 3 is present at location 7. 3 is present at location 10. 3 is present 3 times in the array. Press any key to continue . . .
C program for linear search using function
<span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> linear_search</span><span class="pun">(</span><span class="kwd">long</span><span class="pln"> </span><span class="pun">[],</span><span class="pln"> </span><span class="kwd">long</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">long</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> array</span><span class="pun">[</span><span class="lit">100</span><span class="pun">],</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> position</span><span class="pun">;</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Input number of elements in array\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%ld"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">n</span><span class="pun">);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Input %d numbers\n"</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%ld"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Input number to search\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%ld"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">search</span><span class="pun">);</span><span class="pln"> position </span><span class="pun">=</span><span class="pln"> linear_search</span><span class="pun">(</span><span class="pln">array</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">position </span><span class="pun">==</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">)</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d isn't present in the array.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d is present at location %d.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> position</span><span class="pun">+</span><span class="lit">1</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> linear_search</span><span class="pun">(</span><span class="kwd">long</span><span class="pln"> a</span><span class="pun">[],</span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> find</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">long</span><span class="pln"> c</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">;</span><span class="pln">c </span><span class="pun"><</span><span class="pln"> n </span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++</span><span class="pln"> </span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">a</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> find</span><span class="pun">)</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> c</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span>
Output:
Input number of elements in array 10 Input 10 numbers 9 8 7 6 5 3 2 1 10 2 Input number to search 3 3 is present at location 6. Press any key to continue . . .
Linear search function using pointers
long linear_search(long *pointer, long n, long find) { long c; for (c = 0; c < n; c++) { if (*(pointer+c) == find) return c; } return -1; }
The time required to search an element using linear search algorithm depends on the size of the list. In the best case it is present at beginning of the list and in the worst case element is present at the end. The time complexity of linear search is O(n).
- Question 1: How to do Linear Search in an Array?
- Question 2: Write code to do Linear Search in an Array?
Related Questions
- Assignment 1: Write a program that finds the second largest element in a given list of N numbers.