




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Optional[Any]	,					__UpperCamelCase      :						Any				)  ->							Union[str, Any]:
    UpperCAmelCase_										=					0
    UpperCAmelCase_										=					len(__UpperCamelCase				) - 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

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

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

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




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						str	,					__UpperCamelCase      :						Dict	,					__UpperCamelCase      :						Union[str, Any]	,					__UpperCamelCase      :						Any				)  ->							Optional[int]:

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

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

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

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




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Union[str, Any]				)  ->							Optional[int]:
    if collection != sorted(__UpperCamelCase				):
        raise ValueError('''Collection must be ascending sorted'''				)
    return True


if __name__ == "__main__":
       import sys
       _lowerCamelCase      			=						0
       if debug == 1:
              _lowerCamelCase      			=						[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')
              _lowerCamelCase      			=						67

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











def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						float	,					__UpperCamelCase      :						float				)  ->							float:

    if density <= 0:
        raise ValueError('''Impossible fluid density'''				)
    if bulk_modulus <= 0:
        raise ValueError('''Impossible bulk modulus'''				)

    return (bulk_modulus / density) ** 0.5


if __name__ == "__main__":
 import doctest

 doctest.testmod()





