Linear Search | Searching Algorithms

Searching-

 

  • Searching is a process of finding a particular element among several given elements.
  • The search is said to be successful if the required element is found otherwise the search is unsuccessful.
  • Searching Algorithms are a family of algorithms used for the purpose of searching.

 

Approaches to searching-

 

The searching of an element in a given array can be done in two ways-

  1. Linear Search
  2. Binary Search

 

 

In this article, we will discuss about linear search. Learn about Binary Search here.

 

Linear Search-

 

  • Linear Search is the simplest approach to searching which searches for an element by comparing it with each element of the array one by one.
  • When the required element is successfully found, it returns the index of that element in the array, else it returns -1.
  • Because linear search traverses the array sequentially to locate the element, it is also known as Sequential Search.

 

When Linear Search is applied?

 

Linear Search is applied when-

  • No information is given about the array
  • The given array is unsorted or the elements are unordered
  • The list of data items is smaller

 

Linear Search Algorithm-

 

  • Consider there is a linear array ‘a’ of size ‘n’ and linear search algorithm is being used to search an element ‘item’ in this linear array.
  • If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.

 

Linear_Search (a , n , item , loc)

Begin

for i = 0 to (n – 1) by 1 do

if (a[i] = item) then

set loc = i

Exit

endif

endfor

set loc = -1

End

 

Analysis of Linear Search-

 

Best case-

 

  • In the best possible case, the element we are searching for may be found at the first position.
  • In this case, the search terminates in success with just one comparison.
  • Thus, in best case, the linear search takes O(1) operations.

 

Worst Case-

 

  • In the worst possible case, the element we are searching for may be present at the last position or not present in the array at all.
  • In the former case, the search terminates in success with n comparisons and in the later case, the search terminates in failure with n comparisons.
  • Thus, in worst case, the linear search takes O(n) operations.

 

So, we have-

Time Complexity

Time Complexity of Linear Search = O(n)

where n is the number of elements in the linear array

 

Efficiency of Linear Search-

 

  • Linear Search is less efficient when compared with other algorithms like Binary Search and Hash tables that allow significantly faster searching.

 

Example of Linear Search-

 

Consider we are given the following linear array and we have to search for element 15 in it.

 

 

We will compare the element to be searched (element 15) with all the elements of the given linear array one by one until we find the element 15 or all the elements are searched.

 

Step-01:

 

We compare element 15 with the 1st element 92. Since, 15 ≠ 92, so required element is not found. So, we move to the next element.

 

Step-02:

 

We compare element 15 with the 2nd element 87. Since, 15 ≠ 87, so required element is not found. So, we move to the next element.

 

Step-03:

 

We compare element 15 with the 3rd element 53. Since, 15 ≠ 53, so required element is not found. So, we move to the next element.

 

Step-04:

 

We compare element 15 with the 4th element 10. Since, 15 ≠ 10, so required element is not found. So, we move to the next element.

 

Step-05:

 

We compare element 15 with the 5th element 15. Since, 15 = 15, so required element is found.

Now, we stop the comparison and return index 4 at which the element being searched is present.

 

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Linear Search | Searching Algorithms
Article Name
Linear Search | Searching Algorithms
Description
Searching Algorithms are a family of algorithms used for the purpose of searching elements in a given array. Linear Search and Binary Search are the two famous searching algorithms. Linear Search is the simplest approach to searching which searches for an element by comparing it with each element of the array one by one.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-