Searching Algorithms: Linear Search Algorithm

Searching Algorithms: Linear Search Algorithm

What is searching and types of searching?


We will see the linear search algorithm, but before that let’s understand searching. Searching is an important activity of data structure. In searching, a particular element is searched in an array in order to find its location. This does not matter whether the given element is present or not in the given array. Searching can be sequential or non-sequential. In sequential searching, we traverse the array of elements sequentially and every element is checked. We do that until a match is found or the whole list (array) has been searched. On the other hand in non-sequential searching, we access the elements randomly. If the array is unsorted then we use sequential searching like a linear search algorithm.


The best-case time complexity of the linear search is O(1) while the worst-case time complexity of the linear search is O(n), meaning the time taken by the algorithm to execute is linearly dependent on the input size. If the array is sorted then we can use other searching algorithms like binary search to reduce the time complexity.  Binary search has the time complexity of O(logn). We’ll discuss the binary search in the next section.



The different searching algorithms that we are going to cover in this and upcoming section are:

  1. Linear Search
  2. Binary Search


Table of Contents:


  1. Data Structure & Algorithms: Linear Search Algorithm
  2. Features of Linear search algorithm
  3. Stepwise algorithm and Pseudocode
  4. Linear search implementation in python language with output
  5. Linear search implementation in C++ language with output
  6. Time complexity of linear search (best-case, worst-case, average-case )
  7. Applications of linear search

Data Structure & Algorithms: Linear Search Algorithm


Linear search is a very basic and straight forward search algorithm. In this, we simply start searching the array for the required element from the starting or the leftmost element of the array. One by one we compare and see if the element we are looking for is the one currently to which we’re comparing. If we hit an element in the array which matches the element we’re looking for we return the index of that element. If it doesn’t match we move to the next element. Once we exhaust the elements of the array and we still can’t hit an exact match for the required element, we can conclude that the element is not present in the array and simply returns -1, or we can print “not found”.


Features


  1. It is used for searching an element in an unsorted list or array of small length.
  2. Time complexity of the linear search is O(n), meaning the time taken by the algorithm to execute is linearly dependent on the input size(n). As n increases, the time is taken by the algorithm also increases linearly.
  3. It has a simple implementation.

Linear Search Algorithm


Problem Statement: Search an element ‘x’ in a given array ‘a’ of length ‘n’.

Algorithm:

Linear Search ( array a, length n, element x)

Step 1: Start loop from i = 0 to i < n

Step 2: if a[i] = x then print element x found at index i, and return

Step 3: Outside the loop print element not found and return


Pseudocode:

function linear_search (array, value)
for each item in the array:
	if item==value
		return item’s location
end if
end for
end function

Linear search implementation in Python


Code:


#Code by violet-cat-415996.hostingersite.com
# function
def search(arr, n, x):

    for item in range(0, n):
        if (arr[item] == x):
            return item
    return -1

# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)

# Function call
result = search(arr, n, x)
if(result == -1):
    print("Element not found ! ")
else:
    print("Element is found at index = ", result)

Output:

Element is found at index =  3


Linear search implementation in C++


Code:


//Code by violet-cat-415996.hostingersite.com

#include <iostream>
using namespace std;

int linear_search(int a[], int n, int x)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] == x)
            return i;
    }
    return -1;
}
int main()
{
    int n, x, result;
    cout << "Enter the size of array : " << endl; //Taking size of array
    cin >> n;
    int a[n];

    cout << "Enter " << n << " elements:\n";
    for (int i = 0; i < n; i++)
        cin >> a[i]; //Taking elements of array

    cout << "Enter element to search : ";
    cin >> x; //Taking element to be searched

    result = linear_search(a, n, x); //Calling Function

    if (result == -1)
        cout << "Element not found ! ";
    else
        cout << "Element found at " << result << " index ";

    return 0;
}

Output:

Enter the size of array :                                                                                                                     
3                                                                                                                                             
Enter 3 elements:                                                                                                                             
34 45 56                                                                                                                                      
Enter element to search : 45                                                                                                                  
Element found at 1 index

Time Complexity


  1. Best Case: If the element is found at index 0 that is 1st element of the array matches with x. In this case, the algorithm just performs one comparison and even if we increase the length of the array it won’t affect the time taken by the algorithm as it is just comparing with the first element. Therefore we can say that the time taken by the algorithm is independent of the input size, is constant. Let’s assume the time taken in one comparison is k. The best-case time complexity of the linear search is k = O(1).
  2. Worst Case: If the element is found at index n-1 that is the last element of the array matches with x. In this case, the algorithm has to perform n comparisons. Therefore time taken by the algorithm increases as we increase the input size. Time taken will be nk. The worst-case time complexity of the linear search is nk = O(n).
  3. Average Case (Expected Case):  Average case time complexity is Big O of the sum of all possible runtimes divide by the total no. of possibilities. The algorithm may perform 1 comparison if x matches with the first element of an array, it may perform 2 comparisons if x matches with the second element of an array, it may perform n comparisons if x matches with the last element of an array, or doesn’t found. Therefore, in total, we have n+1 possibilities.

All possible runtimes will be k, 2k, 3k, … nk, nk respectively.

The average-case or expected-case time complexity of the  linear search algorithm is O(n).


Applications


Linear search has simple implementation and therefore it is practical to use when the array has only a few elements, or small length. Since it will iterate over every element in an array it is useful when your array is full of random values i.e., unsorted.


Thanks for reading!

If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies!

Happy Coding!


Introduction to Searching Algorithms: Linear Search Algorithm

Bubble Sort Algorithm In Data Structures & Algorithms using Python

Merge Sort Algorithm in Python

Binary Search in python

Sorting Algorithms and Searching Algorithms in Python

Shutdown Computer with Voice in Python

Tic Tac Toe Python

Guess the Number Python


Share:

Author: Ayush Purawr