Linear Search

1.1 Definition of Linear Search

Linear search (also known as sequential search) is an algorithm for finding an element in a list or array that checks each element sequentially until it finds a match or verifies all elements. It's the simplest search algorithm that doesn't require data to be sorted beforehand.

Main principles:

• Sequential check: The algorithm goes through each element of the array or list, comparing it with the target value.
• Search termination: The search stops when an element matching the target value is found or all elements have been checked.
• No sorting needed: Linear search can be applied to unsorted data.
• Application: Linear search can be used on any data structures that support iteration, including lists and arrays.

Linear search has a time complexity of O(n), where n is the number of elements in the array or list. In the worst case, the algorithm needs to check all n elements to find the target value or determine its absence.

Analysis of time complexity:

• Best case: Element found at the first position, O(1).
• Average case: Element found somewhere in the middle, O(n/2), which is equivalent to O(n).
• Worst case: Element found at the last position or not present, O(n).

1.2 Step-by-step Implementation of Linear Search

Steps of linear search:

• Initialization: Set the initial index for the search (usually the zero index).
• Sequential check: Check each element of the list or array for matching the target value.
• Termination condition: If the element is found, return its index. If all elements are checked and the target value isn't found, return a special value (usually -1 or None).

Implementation of linear search in Python:

def linear_search(arr, target):
    # Go through each element of the array
    for index, element in enumerate(arr):
        # If the current element equals the target value, return its index
        if element == target:
            return index
    # If the element isn't found, return -1
    return -1

Step-by-step explanation of the implementation:

• Loop initialization: A for loop with the enumerate function is used, which returns the index and element of the array on each iteration.
• Comparison: On each iteration, the current element is compared with the target value.
• Return index: If the current element equals the target value, the index of this element is returned.
• Return -1: If the loop completes and the target element is not found, -1 is returned.

# Example of usage:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 2

# Example of usage for an element not in the array:
target = 5
result = linear_search(arr, target)
print(f"Element {target} found at index {result}")  # Output: Element 5 found at index -1

1.3 Examples of Problems Solved with Linear Search

Linear search is used to solve many problems related to searching for elements in data collections. Here are a few examples of such problems:

Problem 1: Finding an Element in an Array

Need to find a given number in an array of numbers.

Example:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Element {target} found at index {index}")  # Output: Element 70 found at index 3

Problem 2: Checking for an Element's Presence in a List

Need to check if a given value is present in a list of strings.

Example:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Element {target} {'found' if found else 'not found'}")  # Output: Element cherry found

Problem 3: Finding the Minimum or Maximum Element

Need to find the minimum or maximum value in a list.

Example:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Minimum value: {min_value}")  # Output: Minimum value: 2

Problem 4: Finding the First Occurrence

Find the first occurrence of a given element in a list.

Example:

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"First occurrence of {target} at index {index}")  # Output: First occurrence of 2 at index 1

Problem 5: Counting Occurrences

Count the number of occurrences of a given element in a list.

Example:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Element {target} occurs {count} times")  # Output: Element 2 occurs 3 times

2

Task

Python SELF EN, level 53, lesson 0

Locked

Linear Search

Linear Search

Open

2

Task

Python SELF EN, level 53, lesson 0

Locked

Searching is Easy

Searching is Easy

Open