How Does Linear Search Work?

Last updated on January 5th, 2025 at 01:14 am

This article explores the Linear Search Algorithm, how does linear search work, its applications, and its implementation in different languages.

1. What is Linear Search Algorithm?

The Linear Search Algorithm is one of the simplest and most intuitive search algorithms. It is a sequential way of finding an element in a given list. Linear search is a special case of brute force search. Its worst case is proportional to the number of elements in the list.

In Linear Search, we start from one end and check every element until the desired element is not found.

2. How Does Linear Search Work?

The Linear Search Algorithm works by iterating through each element of a list or array, starting from the first element and moving sequentially to the last.

If the target element is found, the search is successful, and the index of the element is returned. If the search reaches the end of the list without finding the target, it returns a negative result, indicating the element is not present.

3. Linear Search Algorithm Pseudocode

Simple pseudocode of the Linear Search Algorithm:

function linearSearch(array, target):
    for each element in array:
        if element == target:
            return index of element
    return -1

4. Linear Search Algorithm Flowchart

For a visual representation of the Linear Search Algorithm:

                                      +-----------------+
                                      |  Start          |
                                      +-----------------+
                                             |
                                             |
                                             v
                                      +-----------------+
                                      |  Initialize     |
                                      |  index to 0     |
                                      +-----------------+
                                             |
                                             |
                                             v
                                      +-----------------+
                                      |  Compare target  |
                                      |  with current    |
                                      |  element         |
                                      +-----------------+
                                             |
                                             |
                                             v
                                      +-----------------+
                                      |  If match found,  |
                                      |  return index    |
                                      +-----------------+
                                             |
                                             |
                                             v
                                      +-----------------+
                                      |  If end of list  |
                                      |  reached, return  |
                                      |  -1 (not found)  |
                                      +-----------------+

5. Implementation of Linear Search Algorithm

5.1 Linear Search C++ Implementation

#include <iostream>

int linearSearch(int arr[], int n, int target) {
  for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

int main() {
  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 23;

  int result = linearSearch(arr, n, target);

  if (result != -1) {
    std::cout << "Element found at index " << result << std::endl;
  } else {
    std::cout << "Element not found" << std::endl;
  }

  return 0;
}

5.2 Linear Search Python Program

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i
  return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = linear_search(arr, target)

if result != -1:
  print("Element found at index", result)
else:
  print("Element not found")

5.3 Linear Search Java Implementation

public class LinearSearch {
    public static int linearSearch(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) {
                return i; // If element is found, return its index
            }
        }
        return -1; // If element is not found, return -1
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int x = 10;
        int result = linearSearch(arr, x);
        if (result == -1) {
            System.out.println("Element is not present in array");
        } else {
            System.out.println("Element is present at index " + result);
        }
    }
}

6. Time Complexity of Linear Search

From the analysis of the above pseudocode, it can be observed that with the growth of the input list, average and worst-case complexities also grow linearly.

if there are n elements in the list, the worst-case requires n comparisons.

The complexity of linear Search is expressed as T(n) = O(n).

Time Complexity
Worst Case	O(n)
Best Case	O(1)
Average Case	O(n)
Space Complexity
Worst Case	O(1)

7. Advantages and Disadvantages of Linear Search

7.1 Advantages of Linear Search

• Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
• Not require additional memory.
• It is a well-suited algorithm for small datasets.

7.2 Disadvantages of Linear Search

• Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
• Not suitable for large arrays.

8. Linear Search Recursion

While the Linear Search Algorithm is typically iterative, it can also be implemented recursively. This involves calling the search function within itself, reducing the problem size with each call until the base case is reached.

9. How Many Comparisons in Linear Search?

The number of comparisons in a Linear Search is directly proportional to the size of the list. In the worst-case scenario, where the target element is not present, the algorithm makes n comparisons, where n is the number of elements in the list.

10. When to Use Linear Search

Linear Search Algorithm is suitable for:

1. Small datasets
2. Unordered lists
3. Lists with a small number of unique elements
4. Situations where the cost of sorting the list is higher than the cost of searching

11. When is Linear Search Faster than Binary Search?

Linear Search can be faster than Binary Search in the following scenarios:

• When the cost of accessing an element is very high (e.g., in a database query)
• When the list is very small (e.g., fewer than 10 elements)
• When the list is highly unbalanced (e.g., most elements are concentrated at one end)

FAQs