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:
- Linear Search
- Binary Search
Table of Contents:
- Data Structure & Algorithms: Linear Search Algorithm
- Features of Linear search algorithm
- Stepwise algorithm and Pseudocode
- Linear search implementation in python language with output
- Linear search implementation in C++ language with output
- Time complexity of linear search (best-case, worst-case, average-case )
- 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
- It is used for searching an element in an unsorted list or array of small length.
- 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.
- 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
- 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).
- 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).
- 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
Sorting Algorithms and Searching Algorithms in Python
Shutdown Computer with Voice in Python
