
def 	SCREAMING_SNAKE_CASE__    (      __lowerCAmelCase    ,		__lowerCAmelCase							):
    snake_case__						=				0
    snake_case__						=				len(__lowerCAmelCase							) - 1

    while left <= right:
        # avoid divided by 0 during interpolation
        if sorted_collection[left] == sorted_collection[right]:
            if sorted_collection[left] == item:
                return left
            else:
                return None

        snake_case__						=				left + ((item - sorted_collection[left]) * (right - left)) // (
            sorted_collection[right] - sorted_collection[left]
        )

        # out of range check
        if point < 0 or point >= len(__lowerCAmelCase							):
            return None

        snake_case__						=				sorted_collection[point]
        if current_item == item:
            return point
        else:
            if point < left:
                snake_case__						=				left
                snake_case__						=				point
            elif point > right:
                snake_case__						=				right
                snake_case__						=				point
            else:
                if item < current_item:
                    snake_case__						=				point - 1
                else:
                    snake_case__						=				point + 1
    return None





def 	SCREAMING_SNAKE_CASE__    (      __lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase							):

    # avoid divided by 0 during interpolation
    if sorted_collection[left] == sorted_collection[right]:
        if sorted_collection[left] == item:
            return left
        else:
            return None

    snake_case__						=				left + ((item - sorted_collection[left]) * (right - left)) // (
        sorted_collection[right] - sorted_collection[left]
    )

    # out of range check
    if point < 0 or point >= len(__lowerCAmelCase							):
        return None

    if sorted_collection[point] == item:
        return point
    elif point < left:
        return interpolation_search_by_recursion(__lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase							)
    elif point > right:
        return interpolation_search_by_recursion(__lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase							)
    else:
        if sorted_collection[point] > item:
            return interpolation_search_by_recursion(
                __lowerCAmelCase    ,		__lowerCAmelCase    ,		__lowerCAmelCase    ,		point - 1							)
        else:
            return interpolation_search_by_recursion(
                __lowerCAmelCase    ,		__lowerCAmelCase    ,		point + 1    ,		__lowerCAmelCase							)





def 	SCREAMING_SNAKE_CASE__    (      __lowerCAmelCase							):
    if collection != sorted(__lowerCAmelCase							):
        raise ValueError("Collection must be ascending sorted"							)
    return True


if __name__ == "__main__":
     import sys
     __magic_name__            =  0
     if debug == 1:
          __magic_name__            =  [10, 30, 40, 45, 50, 66, 77, 93]
          try:
               __assert_sorted(collection)
          except ValueError:
               sys.exit('''Sequence must be ascending sorted to apply interpolation search''')
          __magic_name__            =  67

     __magic_name__            =  interpolation_search(collection, target)
     if result is not None:
          print(F'''{target} found at positions: {result}''')
     else:
          print('''Not found''')





from __future__ import annotations





def 	SCREAMING_SNAKE_CASE__    (      __lowerCAmelCase    ,		__lowerCAmelCase							):
    if len(__lowerCAmelCase							) == 0:
        return False
    snake_case__						=				len(__lowerCAmelCase							) // 2
    if a_list[midpoint] == item:
        return True
    if item < a_list[midpoint]:
        return binary_search(a_list[:midpoint]    ,		__lowerCAmelCase							)
    else:
        return binary_search(a_list[midpoint + 1 :]    ,		__lowerCAmelCase							)


if __name__ == "__main__":
     __magic_name__            =  input('''Enter numbers separated by comma:\n''').strip()
     __magic_name__            =  [int(item.strip()) for item in user_input.split(''',''')]
     __magic_name__            =  int(input('''Enter the number to be found in the list:\n''').strip())
     __magic_name__            =  '''''' if binary_search(sequence, target) else '''not '''
     print(F'''{target} was {not_str}found in {sequence}''')



