# Counters for counting steps taken in linear search and binary search
ls_counter = 0
bs_counter = 0

def linear_search(lst, x):
    """Returns the index of the element x in lst or -1 if it doesn't exist"""
    for i in range(len(lst)):
        # INCREMENT COUNTER HERE!

        if lst[i] == x:
            return i

    # Return -1 if x is not found
    return -1

def binary_search(sorted_lst, x):
    """Returns the index of the element x in lst or -1 if it doesn't exist"""
    return binary_search_range(sorted_lst, x, 0, len(sorted_lst)-1)

def binary_search_range(sorted_lst, x, left_index, right_index):
    # If there are no elements in the range
    if right_index < left_index:
        # Then x is certainly not here, so return -1
        return -1
    else:
        # INCREMENT COUNTER HERE!

        # Find the middle element
        mid_index = (left_index + right_index) // 2
        mid_value = sorted_lst[mid_index]

        # If the middle element is equal to x, we're done!
        if mid_value == x:
            return mid_index

        # If x is to the left of the middle element, search the left half
        elif x < mid_value:
            return binary_search_range(sorted_lst, x, left_index, mid-1)

        # If x is to the right of the middle element, search the right half
        else:
            return binary_search_range(sorted_lst, x, mid+1, right_index)

def ls_experiment(n, x):
    global ls_count
    ls_count = 0
    lst = list(range(n))
    linear_search(lst, x)
    print("steps:", ls_count)

def bs_experiment(n, x):
    global ls_count
    bs_count = 0
    lst = list(range(n))
    binary_search(lst, x)
    print("steps:", ls_count)