Linear Search

def linear_search(arr, target):
    """
    Search for target in array using linear search
    Returns index if found, -1 if not found
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

def linear_search_with_steps(arr, target):
    """Linear search with step-by-step visualization"""
    print(f"Searching for {target} in {arr}")
    
    for i in range(len(arr)):
        print(f"Step {i+1}: Checking arr[{i}] = {arr[i]}")
        
        if arr[i] == target:
            print(f"✅ Found {target} at index {i}")
            return i
        else:
            print(f"❌ {arr[i]} ≠ {target}, continue...")
    
    print(f"❌ {target} not found in array")
    return -1

# Test the algorithm
test_array = [10, 23, 45, 70, 11, 15]
target = 70

print("=== Basic Linear Search ===")
result = linear_search(test_array, target)
print(f"Result: {result}")

print("\n=== Step-by-step Linear Search ===")
result = linear_search_with_steps(test_array, target)
                                

def find_all_occurrences(arr, target):
    """Find all indices where target appears"""
    indices = []
    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)
    return indices

def find_first_occurrence(arr, target):
    """Find first occurrence of target"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

def find_last_occurrence(arr, target):
    """Find last occurrence of target"""
    last_index = -1
    for i in range(len(arr)):
        if arr[i] == target:
            last_index = i
    return last_index

def count_occurrences(arr, target):
    """Count how many times target appears"""
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

def linear_search_with_condition(arr, condition_func):
    """Search for first element that satisfies condition"""
    for i, element in enumerate(arr):
        if condition_func(element):
            return i, element
    return -1, None

# Test variations
test_data = [5, 2, 8, 2, 9, 1, 2, 4]

print("Array:", test_data)
print(f"All occurrences of 2: {find_all_occurrences(test_data, 2)}")
print(f"First occurrence of 2: {find_first_occurrence(test_data, 2)}")
print(f"Last occurrence of 2: {find_last_occurrence(test_data, 2)}")
print(f"Count of 2: {count_occurrences(test_data, 2)}")

# Search with condition (find first even number > 5)
index, value = linear_search_with_condition(test_data, lambda x: x > 5 and x % 2 == 0)
print(f"First even number > 5: {value} at index {index}")
                                

def search_strings(string_list, target):
    """Linear search on strings"""
    for i, string in enumerate(string_list):
        if string == target:
            return i
    return -1

def search_case_insensitive(string_list, target):
    """Case-insensitive string search"""
    target_lower = target.lower()
    for i, string in enumerate(string_list):
        if string.lower() == target_lower:
            return i
    return -1

def search_objects(obj_list, key, value):
    """Search objects by attribute"""
    for i, obj in enumerate(obj_list):
        if hasattr(obj, key) and getattr(obj, key) == value:
            return i
    return -1

def search_nested_lists(matrix, target):
    """Search in 2D array/matrix"""
    for i, row in enumerate(matrix):
        for j, element in enumerate(row):
            if element == target:
                return (i, j)
    return (-1, -1)

# Test different data types
print("=== String Search ===")
fruits = ["apple", "banana", "orange", "grape", "kiwi"]
result = search_strings(fruits, "orange")
print(f"'orange' found at index: {result}")

print("\n=== Case-insensitive Search ===")
names = ["Alice", "BOB", "Charlie", "diana"]
result = search_case_insensitive(names, "bob")
print(f"'bob' found at index: {result}")

print("\n=== Object Search ===")
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)]
result = search_objects(people, "name", "Bob")
print(f"Person named 'Bob' found at index: {result}")

print("\n=== 2D Array Search ===")
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
result = search_nested_lists(matrix, 5)
print(f"Value 5 found at position: {result}")