*What is searching and types of searching?*

*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:*

*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*

*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 **

**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*

*Linear Search Algorithm*

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

__Algorithm:__

__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:__

__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*

*Linear search implementation in Python*

### Code:

#Code by copyassignment.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++*

*Linear search implementation in C++*

### Code:

//Code by copyassignment.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 1
^{st}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*

*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