Purva09/algorithm-battlefield

1"""Searching Algorithms"""2 3def linear_search(arr, target):4    """Linear Search - Searches sequentially through the array"""5    for i in range(len(arr)):6        if arr[i] == target:7            return i8    return -19 10 11def binary_search(arr, target):12    """Binary Search - Searches sorted array by dividing in half"""13    arr_sorted = sorted(arr)14    left, right = 0, len(arr_sorted) - 115    16    while left <= right:17        mid = (left + right) // 218        if arr_sorted[mid] == target:19            return mid20        elif arr_sorted[mid] < target:21            left = mid + 122        else:23            right = mid - 124    25    return -126 27 28def fibonacci_search(arr, target):29    """Fibonacci Search - Uses Fibonacci numbers to divide search space"""30    arr_sorted = sorted(arr)31    n = len(arr_sorted)32    33    # Initialize fibonacci numbers34    fib2 = 0  # (m-2)'th Fibonacci number35    fib1 = 1  # (m-1)'th Fibonacci number36    fib = fib2 + fib1  # m'th Fibonacci number37    38    while fib < n:39        fib2 = fib140        fib1 = fib41        fib = fib2 + fib142    43    offset = -144    45    while fib > 1:46        i = min(offset + fib2, n - 1)47        48        if arr_sorted[i] < target:49            fib = fib150            fib1 = fib251            fib2 = fib - fib152            offset = i53        elif arr_sorted[i] > target:54            fib = fib255            fib1 = fib1 - fib256            fib2 = fib - fib157        else:58            return i59    60    if fib1 and offset + 1 < n and arr_sorted[offset + 1] == target:61        return offset + 162    63    return -164