##############################
##         IMPORTS         ##
##############################
import numpy as np

##############################
##       LINEAR SEARCH      ##
##############################
def linear_search (my_list, element):
    """
        Brute force search of an element in a list. The list
        does not have to be sorted
        Inputs:
            my_list (a list)
            element (int/float/string): the element to be found in the list  
        Returns
            i (an int): returns the index where the element was found, returns
                -1 if the element was not found            
    """
    length = len(my_list)
    for i in range(length):
        if my_list[i] == element:
            return i
    return -1

##############################
##       BINARY SEARCH      ##
##############################
def binary_search(my_list, element):
    """
        Searches for an element in a sorted list by dividing the search
        space in half
        Inputs:
            my_list (a sorted list)
            element (int/float/string): the element to be found in the list
        Returns
            mid (an int): returns the index where the element was found, returns
                -1 if the element was not found
    """
    # Set the initial boundaries
    left = 0
    right = len(my_list) - 1
    
    while left <= right:
        # Find the midpoint
        mid = left + (right - left) // 2

        # If the midpoint is the element to find
        if my_list[mid] == element:
            return mid
        # If the midpoint is less than the element then
        # move the left point
        elif my_list[mid] < element:
            left = mid + 1
        # If the midpoint is greater than the element, move
        # the right point
        else:
            right = mid - 1
    
    return -1

##############################
##        JUMP SEARCH       ##
##############################
def jump_search(my_list, element):
    """
        Searches for an element in a sorted list jumping to the block of a set size
        that should contain the element and then doing a linear search
        Inputs:
            my_list (a sorted list)
            element (int/float/string): the element to be found in the list
        Returns
            mid (an int): returns the index where the element was found, returns
                -1 if the element was not found
    """    
    n = len(my_list)
    m = int(np.sqrt(n))  # Block size to be jumped
    prev = 0
    curr = 0
    
    # Jump ahead to find the block where the element may be present
    while curr < n and my_list[curr] < element:
        prev = curr
        curr += m
        if curr >= n:
            curr = n
    
    # Perform a linear search in the identified block
    for i in range(prev, min(curr, n)):
        if my_list[i] == element:
            return i
    
    return -1

##############################
##     MAKE SEARCH LIST     ##
##############################
def make_search_list (length, max_val, ensured_val):
    """
        Creates a list of integers of a given length between zero and one less than
        the maximum value passed. Then, it ensures that a given value is randomly placed
        in the list
        Inputs:
            length (an int): the length of the list
            max_val (an int): the maximum value (+1) to include in the list of integers
            ensured_val (int/float): the value to make sure is in the list
        Returns:
            my_list(a numpy array): a list of integers with the wanted element randomly placed
                in the list
    """
    my_list = np.random.randint(0, max_val, length)
    random_index = np.random.randint(length)
    my_list[random_index] = ensured_val
    return my_list

## Test Usage
my_list = make_search_list(100, 100, 3) 

print((my_list==3).sum()) # Print the number of occurrences of the wanted element

print(linear_search(my_list, 3)) # Does not have to be sorted for linear search

my_list = sorted(my_list) # Binary and jump search need a sorted list

print(binary_search(my_list, 3))
print(jump_search(my_list, 3))

2
57
2
2