
from testing.search import test_search, test_search_bool


# linear search
def linear_search(arr, target):
    """
    Searches for the first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(n)
    Space Complexity = O(1)
    """
    for idx in range(len(arr)):
        if arr[idx] == target: return idx
    return None


def linear_search_multiple(arr, target):
    """
    Searches the provided target in the given array.
    If target(s) found, then a list with index(es) will be returned.
    else empty list will be returned.
    Time Complexity = O(n)
    Space Complexity = O(1)
    """
    return [idx for idx in range(len(arr)) if arr[idx] == target]

# binary search 

def binary_search(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    first = 0; last = len(arr) - 1
    while first <= last:
        # calculate mid point
        mid = (last + first) // 2
        # target found then return else adjust first and last
        if arr[mid] == target: 
            return mid
        if arr[mid] > target:
            # search left
            last = mid - 1
        if arr[mid] < target:
            # search right
            first = mid + 1
    return None

def binary_search_multiple(arr, target):
    """
    Searches the provided target in the given array.
    If target(s) found, then a list with index(es) will be returned.
    else empty list will be returned.
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    pass

def binary_search_recursive(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    pass

def binary_search_recursive_bool(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns True, else False
    Time Complexity = O(log n)
    Space Complexity = O(log n)
    """
    mid = len(arr) // 2
    # base conditions
    if len(arr) == 0:
        return False
    if arr[mid] == target:
        return True
    # rescursions
    if arr[mid] > target:
        # search left
        return binary_search_recursive_bool(arr=arr[:mid], target=target)
    if arr[mid] < target:
        # search right
        return binary_search_recursive_bool(arr=arr[mid+1:], target=target)



arr1 = [1, 33, 2, 4, 1, 3, 91, 2]
arr2 = [1, 4, 33, 50, 81, 91, 100]
test_search(arr=arr1, func=linear_search)
test_search(arr=arr2, func=binary_search)
test_search_bool(arr=arr2, func=binary_search_recursive_bool)





from testing.search import test_search, test_search_bool


# linear search
def linear_search(arr, target):
    """
    Searches for the first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(n)
    Space Complexity = O(1)
    """
    for idx in range(len(arr)):
        if arr[idx] == target: return idx
    return None


def linear_search_multiple(arr, target):
    """
    Searches the provided target in the given array.
    If target(s) found, then a list with index(es) will be returned.
    else empty list will be returned.
    Time Complexity = O(n)
    Space Complexity = O(1)
    """
    return [idx for idx in range(len(arr)) if arr[idx] == target]

# binary search 

def binary_search(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    first = 0; last = len(arr) - 1
    while first <= last:
        # calculate mid point
        mid = (last + first) // 2
        # target found then return else adjust first and last
        if arr[mid] == target: 
            return mid
        if arr[mid] > target:
            # search left
            last = mid - 1
        if arr[mid] < target:
            # search right
            first = mid + 1
    return None

def binary_search_multiple(arr, target):
    """
    Searches the provided target in the given array.
    If target(s) found, then a list with index(es) will be returned.
    else empty list will be returned.
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    pass

def binary_search_recursive(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns index of it, else None
    Time Complexity = O(log n)
    Space Complexity = O(1)
    """
    pass

def binary_search_recursive_bool(arr, target):
    """
    Searches for first occurance of the provided target in the given array.
    If target found then returns True, else False
    Time Complexity = O(log n)
    Space Complexity = O(log n)
    """
    mid = len(arr) // 2
    # base conditions
    if len(arr) == 0:
        return False
    if arr[mid] == target:
        return True
    # rescursions
    if arr[mid] > target:
        # search left
        return binary_search_recursive_bool(arr=arr[:mid], target=target)
    if arr[mid] < target:
        # search right
        return binary_search_recursive_bool(arr=arr[mid+1:], target=target)



arr1 = [1, 33, 2, 4, 1, 3, 91, 2]
arr2 = [1, 4, 33, 50, 81, 91, 100]
test_search(arr=arr1, func=linear_search)
test_search(arr=arr2, func=binary_search)
test_search_bool(arr=arr2, func=binary_search_recursive_bool)




# linear search Searches for the first occurance of the provided target in the given array.     If target found then returns index of it, else None     Time Complexity = O(n)     Space Complexity = O(1) Searches the provided target in the given array.     If target(s) found, then a list with index(es) will be returned.     else empty list will be returned.     Time Complexity = O(n)     Space Complexity = O(1) # binary search Searches for first occurance of the provided target in the given array.     If target found then returns index of it, else None     Time Complexity = O(log n)     Space Complexity = O(1) # calculate mid point # target found then return else adjust first and last # search left # search right Searches the provided target in the given array.     If target(s) found, then a list with index(es) will be returned.     else empty list will be returned.     Time Complexity = O(log n)     Space Complexity = O(1) Searches for first occurance of the provided target in the given array.     If target found then returns index of it, else None     Time Complexity = O(log n)     Space Complexity = O(1) Searches for first occurance of the provided target in the given array.     If target found then returns True, else False     Time Complexity = O(log n)     Space Complexity = O(log n) # base conditions # rescursions # search left # search right