



def      _lowerCAmelCase			(   __lowerCAmelCase    ,    __lowerCAmelCase )  ->   Dict:


				"""simple docstring"""

				snake_case__      : Optional[Any]							=      0
				snake_case__      : List[Any]							=      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

								snake_case__      : int							=      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

								snake_case__      : Tuple							=      sorted_collection[point]
								if current_item == item:
												return point
								else:
												if point < left:
																snake_case__      : int							=      left
																snake_case__      : str							=      point
												elif point > right:
																snake_case__      : Tuple							=      right
																snake_case__      : int							=      point
												else:
																if item < current_item:
																				snake_case__      : Dict							=      point - 1
																else:
																				snake_case__      : List[Any]							=      point + 1
				return None



def      _lowerCAmelCase			(   __lowerCAmelCase    ,    __lowerCAmelCase    ,    __lowerCAmelCase    ,    __lowerCAmelCase )  ->   int:


				"""simple docstring"""

				if sorted_collection[left] == sorted_collection[right]:
								if sorted_collection[left] == item:
												return left
								else:
												return None

				snake_case__      : Optional[int]							=      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      _lowerCAmelCase			(   __lowerCAmelCase )  ->   Optional[Any]:


				"""simple docstring"""

				if collection != sorted(UpperCamelCase__ ):
								raise ValueError('''Collection must be ascending sorted''' )
				return True


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

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


'''simple docstring'''




def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							)      ->       float:
    return base * power(UpperCamelCase__							,    (exponent - 1)							) if exponent else 1


if __name__ == "__main__":
  print("Raise base to the power of exponent using recursion...")
  __UpperCAmelCase					=int(input("Enter the base: ").strip())
  __UpperCAmelCase					=int(input("Enter the exponent: ").strip())
  __UpperCAmelCase					=power(base, abs(exponent))
  if exponent < 0:  # power() does not properly deal w/ negative exponents
    __UpperCAmelCase					=1 / result
  print(f'{base} to the power of {exponent} is {result}')
