algorithms.py

# ============================================================
# Introduction to Algorithms
# Covers:
# 1. Linear Search
# 2. Binary Search
# 3. Recursive Binary Search
# ============================================================

import time

def main():
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    
    while True:
        print("\nWelcome to the Algorithms Playground")
        print("--------------------------------")
        print("1. Linear Search")
        print("2. Binary Search")
        print("3. Recursive Binary Search")
        print("4. Exit")
        print("--------------------------------")
        choice = int(input("Enter your choice: "))
        
        if choice == 1:
            target = int(input("Enter a target number: "))
            result = linear_search(numbers, target)
            verify(result)
        elif choice == 2:
            target = int(input("Enter a target number: "))
            result = binary_search(numbers, target)
            verify(result)
        elif choice == 3:
            target = int(input("Enter a target number: "))
            result = recursive_binary_search(numbers, target)
            verify(result)
        elif choice == 4:
            print("Exiting...")
            break
        else:
            print("Invalid choice")

# ------------------------------------------------------------
# LINEAR SEARCH
# ------------------------------------------------------------

def linear_search(arr, target):
    """
    Returns the index of the target element in the array else returns None
    """
    # Print the target and the array being searched
    print(f"Searching for {target} in array: {arr}")
    print("Starting linear search...")
    time.sleep(1)
    
    # Iterate over each element in the array
    for i in range(len(arr)):
        # Print the current index and element being checked
        print(f"Checking index {i}: {arr[i]}", end="")
        time.sleep(0.5)
        
        # Check if the current element matches the target
        if arr[i] == target:
            print(" ✓ MATCH!")  # Print match found
            return i  # Return the index of the target
        else:
            print(" ✗")  # Print no match
    
    # Print message if target is not found in the array
    print("Reached end of array - target not found")
    return None



# ------------------------------------------------------------
# BINARY SEARCH
# ------------------------------------------------------------

def binary_search(arr, target):
    """
    Returns the index of the target element in the array else returns None
    """
    print(f"Searching for {target} in sorted array: {arr}")
    print("Starting binary search...")
    time.sleep(1)
    
    first = 0
    last = len(arr) - 1
    step = 1

    # Iterate over the array
    while first <= last:    
        midpoint = (first + last) // 2
        
        # Show current search space
        search_space = arr[first:last+1]
        print(f"\nStep {step}:")
        print(f"Search space: {search_space} (indices {first}-{last})")
        print(f"Checking middle element at index {midpoint}: {arr[midpoint]}", end="")
        time.sleep(0.8)
        
        # Check if the current element matches the target
        if arr[midpoint] == target:
            print(" ✓ MATCH!")
            return midpoint
        # If the current element is less than the target, move the first pointer to the right
        elif arr[midpoint] < target:
            print(f" ✗ Too small! Searching right half...")
            first = midpoint + 1
        # If the current element is greater than the target, move the last pointer to the left
        else:
            print(f" ✗ Too big! Searching left half...")
            last = midpoint - 1
        
        step += 1
        time.sleep(0.5)
    
    # Print message if target is not found in the array
    print(f"\nSearch space exhausted - target not found")
    return None # Return None if target is not found



# ------------------------------------------------------------
# RECURSIVE BINARY SEARCH
# ------------------------------------------------------------

def recursive_binary_search(arr, target):
    """
    Returns the index of the target element in the array else returns None
    """
    print(f"Searching for {target} in sorted array: {arr}")
    print("Starting recursive binary search...")
    time.sleep(1)

    if len(arr) == 0:
        return None
    else:
        midpoint = len(arr) // 2
    
        if arr[midpoint] == target:
            print(f" ✓ MATCH!")
            return midpoint
        elif arr[midpoint] < target:
            print(f" ✗ Too small! Searching right half...")
            return recursive_binary_search(arr[midpoint+1:], target)
        else:
            print(f" ✗ Too big! Searching left half...")
            return recursive_binary_search(arr[:midpoint], target)
    
    print("Reached end of array - target not found")
    return None # Return None if target is not found


def verify(index):
    # Check if the target was found and print the result
    if index is not None:
        # Print the index of the target
        print(f"Target found at index: {index}")
    else:
        print("Target not found in array")

if __name__ == "__main__":
    main()