Linear Search Algorithm in Python.

Given an integer array arr[] of size n and an element x, the task is to write a Python program to search for the element x in the given array.

Example:

Input: arr = [12, 10, 9, 11, 41] x = 9
Output: X is present at index 2.

Input: arr = [1, 2, 3, 4, 6, 9] x = 7
Output: Not Found

Input: arr = [-1, 2, 4] x = 2
Output: X is present at index 1

There are two popular algorithms one is Linear Search and another is Binary Search for searching an element in an array. In this article, we are going to learn how to use the Linear Search algorithm in Python programming.

Linear Search Algorithm.

Linear search, also known as sequential search, is a straightforward searching algorithm where we start from the beginning of the array and compare each element with the target value until a match is found or the entire array has been traversed.

Below are the algorithm steps to do the linear search:

Step 1: Start from the first element of the array.

Step 2: Compare the current element with the target value x.

Step 3: If the element is equal to the target x, return the index.

Step 4: If not, move to the next element.

Step 5: Repeat steps 2-4 until the target is found or the end of the array is reached.

Step 6: If the target is not found after traversing the entire array, return -1.

Python Program for Linear Search.

Below is the Python code implementation of Linear search using an iterative method.

# Python code to search element using Linear Search
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Target found, return the index
    return -1  # Target not found

# Example usage
array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target_value = 6
result = linear_search(array, target_value)

if result != -1:
    print(f'Target {target_value} found at index {result}.')
else:
    print(f'Target {target_value} not found in the array.')

Output:

Target 6 found at index 7.

Time Complexity: The worst-case time complexity is O(n) when the target element is present at the end of the array.

Space Complexity: O(1) - Linear search is an "in-place" algorithm that doesn't require additional memory proportional to the input size.

Python Program for Linear Search Using Recursion.

In this recursive algorithm, we have two base cases: first, if the current element equals the target, it returns the current index; second, if the current index surpasses the array length, indicating the target is not present, it returns -1.

In the recursive case, the function calls itself with an incremented index to continue the search in the remaining array. This process repeats until one of the base cases is met.

Below is the Python code implementation of Linear search using recursion.

Python Code.

# Python program to search element using Recursive Method
def linear_search(arr, target, current_index=0):
    # Base case: target found
    if current_index < len(arr):
        if arr[current_index] == target:
            return current_index
    
    # Base case: target not found
    if current_index == len(arr):
        return -1
    
    # Recursive case: search in the remaining array
    return linear_search_recursive(arr, target, current_index + 1)

# Example
arr = [1, 2, 3, 4, 5]
target = 3

result = linear_search(arr, target)

if result != -1:
    print(f"Target {target} found at index {result}.")
else:
    print(f"Target {target} not found in the array.")

Output:

Target 3 found at index 2.

Time Complexity: Linear search has a time complexity of O(n) in the worst case.
Space Complexity: The recursive calls use the call stack, and in the worst case, the space complexity is O(n) due to the depth of the recursion.

Linear Search Algorithm in Python.

Linear Search Algorithm.

Python Program for Linear Search.

Python Program for Linear Search Using Recursion.

No comments:

Post a Comment