Linear Search

Problem

Linear Search is the simplest searching algorithm that checks each element in the list sequentially until the desired element is found or the list ends.

Examples:

Example 1:
Input: arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170], target = 110
Output: 6 (index of target value)
Explanation: The algorithm sequentially checks each element and finds the target value 110 at index 6.

Example 2:
Input: arr = [10, 20, 80, 30, 60, 50], target = 100
Output: -1 (target not found)
Explanation: The algorithm checks all elements but doesn't find the target value 100, so it returns -1.

Solution

Intuition

  • Linear Search is a straightforward algorithm that works on both sorted and unsorted arrays.
  • It sequentially checks each element of the list until a match is found or the whole list has been searched.
  • While it's not the most efficient for large datasets, it's simple to implement and works well for small lists.
  • It doesn't require the list to be sorted, unlike binary search.

Approach

  • Start from the leftmost element of the array and compare each element with the target value.
  • If the element matches the target value, return its index.
  • If the element doesn't match, move to the next element.
  • If no match is found after checking all elements, return -1 to indicate the target is not present in the array.

Complexity Analysis

  • Time Complexity: O(n) in the worst case, where n is the number of elements in the array. This occurs when the target is the last element or not present in the array.
  • Space Complexity: O(1) as it only requires a constant amount of additional memory regardless of the input size.
Implementation
CPP
Run your code to see output here