
"""simple docstring"""

def 		UpperCAmelCase (		a_,						a_      ):





		'''simple docstring'''


		lowerCamelCase					:      int          =   0
		lowerCamelCase					:      Dict          =   len(lowercase_      ) - 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

				lowerCamelCase					:      Optional[Any]          =   left + ((item - sorted_collection[left]) * (right - left)) // (
				    sorted_collection[right] - sorted_collection[left]
				)

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

				lowerCamelCase					:      Optional[Any]          =   sorted_collection[point]
				if current_item == item:
						return point
				else:
						if point < left:
								lowerCamelCase					:      Dict          =   left
								lowerCamelCase					:      List[Any]          =   point
						elif point > right:
								lowerCamelCase					:      Optional[Any]          =   right
								lowerCamelCase					:      Any          =   point
						else:
								if item < current_item:
										lowerCamelCase					:      Union[str, Any]          =   point - 1
								else:
										lowerCamelCase					:      Union[str, Any]          =   point + 1
		return None
def 		UpperCAmelCase (		a_,						a_,						a_,						a_      ):





		'''simple docstring'''


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

		lowerCamelCase					:      List[str]          =   left + ((item - sorted_collection[left]) * (right - left)) // (
		    sorted_collection[right] - sorted_collection[left]
		)

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

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





		'''simple docstring'''


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


if __name__ == "__main__":
					import sys
					_A						=			0
					if debug == 1:
										_A						=			[1_0, 3_0, 4_0, 4_5, 5_0, 6_6, 7_7, 9_3]
										try:
															__assert_sorted(collection)
										except ValueError:
															sys.exit('Sequence must be ascending sorted to apply interpolation search')
										_A						=			6_7

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








"""simple docstring"""

def 		UpperCAmelCase (		a_ = 10      ):





		'''simple docstring'''


		if not isinstance(a_,						a_      ) or n < 0:
				raise ValueError('Invalid input'      )
		lowerCamelCase					:      Union[str, Any]          =   10**n
		lowerCamelCase					:      int          =   2_8433 * (pow(2,						783_0457,						a_      )) + 1
		return str(number % modulus      )


if __name__ == "__main__":
					from doctest import testmod

					testmod()
					print(F"""{solution(1_0) = }""")






