Guided Project: Searching Algorithms

Linear Search

Example Implementation

                        def linear_search(array, target):
    # Loop through each element in the array
    for i, value in enumerate(array):
        # If the current element matches the target
        if value == target:
            return i  # Return the index where found
    # If target is not found in the array
    return -1
                    

Time & Space Complexity:

Time Complexity: O(n) - In the worst case, we need to check every element
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

numbers = [5, 12, 8, 44]
print(linear_search(numbers, 12))  # 1
print(linear_search(numbers,10

Binary Search

Example Implementation

                        def binary_search(sorted_array, target):
    left = 0
    right = len(sorted_array) - 1
    while left <= right:
        middle = (left + right) // 2
        if sorted_array[middle] == target:
            return middle
        if sorted_array[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1
                    

Time & Space Complexity:

Time Complexity: O(log n) - We eliminate half of the remaining elements at each step
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

sorted_numbers = [1, 5, 8, 12, 20, 45, 67, 99]
print(binary_search(sorted_numbers, 12))  # 3
print(binary_search(sorted_numbers, 10))  # -1

Recursive Binary Search

Example Implementation

                        def recursive_binary_search(sorted_array, target, left=0, right=None):
    if right is None:
        right = len(sorted_array) - 1
    if left > right:
        return -1
    middle = (left + right) // 2
    if sorted_array[middle] == target:
        return middle
    if sorted_array[middle] > target:
        return recursive_binary_search(sorted_array, target, left, middle - 1)
    return recursive_binary_search(sorted_array, target, middle + 1, right)

                    

Time & Space Complexity:

Time Complexity: O(log n) - Same as iterative binary search
Space Complexity: O(log n) - Due to the recursive call stack

Example Usage:

sorted_numbers = [1, 5, 8, 12, 20, 45, 67, 99]
print(recursive_binary_search(sorted_numbers, 12))  # 3
print(recursive_binary_search(sorted_numbers, 10))  # -1

Practice Challenges

Challenge 1: Find First and Last Position

Given a sorted array of integers and a target value, find the starting and ending position of the target value.

                        def search_range(nums, target):
    # Your code here
    pass
                    

Example:

print(search_range([5, 7, 7, 8, 10, 8))  # Output: [3, 5]
print(search_range([5, 7, 7, 8, 10, 6))  # Output: [-1, -1]

Additional Resources:

If you want more practice with search algorithms, check out these LeetCode problems: