Explanation

• Concept: Linear search is a simple search algorithm that sequentially checks each element in a list or array until the target element is found or the list is exhausted.
• Process: Linear search compares the target value with each element in the list, starting from the first element and moving to the last.
• Steps:
  • Start from the first element of the list.
  • Compare the current element with the target value.
  • If the element matches the target, return its index.
  • If the element does not match, move to the next element.
  • Repeat this process until the target is found or the end of the list is reached.
• Efficiency: Linear search has a time complexity of O(n), where n is the number of elements in the list. It is simple but not very efficient for large datasets.

Algorithm Recap

• Loop: Iterate through the list from the first element to the last.
• • If the current element matches the target, return its index.
  • If the end of the list is reached without finding the target, return -1.
• Endcondition: When the loop completes without finding the target, return -1.

Considerations

• Linear search is simple and easy to implement, but it is not efficient for large datasets.
• It is useful when the list is unsorted or when you need to find the first occurrence of an element.

Complexity Analysis

• Time: O(n) because in the worst case, every element may need to be checked.
• Space:

  O(1), as no additional data structures are used.

  • Uses O(1) space, as it only requires a few variables without allocating additional data structures.

Python Implementation

      
          from typing import List

def linear_search(arr: List[int], target: int) -> int:
    for i in range(len(arr)): # Iterate through the list
        if arr[i] == target:    # Check if the current element matches the target
            return i            # Return the index if found
    return -1                  # Return -1 if target is not found 

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    target = int(input("Enter target: "))
    res = linear_search(arr, target)
    print("Index of target:", res)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Target in Middle

  Input:

  • Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
  • Target: 5

  Expected Output: 4

  Explanation: The target 5 is located at index 4 (using 0-based indexing).

• Target is First Element

  Input:

  • Array: [1, 2, 3, 4, 5]
  • Target: 1

  Expected Output: 0

  Explanation: The target 1 is the first element, which is at index 0.

• Target is Last Element

  Input:

  • Array: [1, 2, 3, 4, 5]
  • Target: 5

  Expected Output: 4

  Explanation: The target 5 is the last element, at index 4.

• Target Not Present

  Input:

  • Array: [2, 4, 6, 8, 10]
  • Target: 7

  Expected Output: -1

  Explanation: Since 7 is not in the array, the function returns -1.

• Single Element - Target Present

  Input:

  • Array: [10]
  • Target: 10

  Expected Output: 0

  Explanation: The only element is 10, located at index 0.

• Empty Array

  Input:

  • Array: []
  • Target: 3

  Expected Output: -1

  Explanation: An empty array returns -1 because the target cannot be found.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"arr": [1, 2, 3, 4, 5, 6, 7, 8, 9], "target": 5, "expected": 4},
        {"arr": [1, 2, 3, 4, 5], "target": 1, "expected": 0},
        {"arr": [1, 2, 3, 4, 5], "target": 5, "expected": 4},
        {"arr": [2, 4, 6, 8, 10], "target": 7, "expected": -1},
        {"arr": [10], "target": 10, "expected": 0},
        {"arr": [], "target": 3, "expected": -1},
    ]
    
    for i, test in enumerate(tests, 1):
        result = linear_search(test["arr"], test["target"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")

if __name__ == "__main__":
    run_tests() 

        

Usage and Applications