February 8, 2025

Linear Search in Python

Linear Search is the simplest searching algorithm used to find an element in an unsorted or sorted array. The main idea behind Linear Search is to sequentially check each element of the array until the target value is found or the entire array has been searched.

How Linear Search Works

  1. Start from the first element of the array.
  2. Compare the current element with the target value.
  3. If the current element is equal to the target value, return the index of the current element.
  4. If the current element is not equal to the target value, move to the next element.
  5. Repeat the process until the target value is found or the end of the array is reached.
  6. If the target value is not found, return -1.

Python Implementation of Linear Search

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

# Example usage:
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = linear_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
    

Explanation of the Code

  • The function linear_search(arr, x) takes an array arr and a target value x as input.
  • The function iterates over each element in the array using a for loop.
  • If the current element arr[i] matches the target value x, the function returns the index i.
  • If no match is found after checking all elements, the function returns -1.

Complexity Analysis

Linear Search has a time complexity of O(n) because it may need to check each element in the array in the worst case. This makes it less efficient than more advanced search algorithms, especially for large datasets.

Space complexity is O(1) because it only requires a constant amount of additional space.