






"""simple docstring"""






def  __lowerCamelCase					(					lowerCAmelCase__       ,lowerCAmelCase__				):
				A__							 =       0
				A__							 =       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

								A__							 =       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

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



def  __lowerCamelCase					(					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

				A__							 =       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  __lowerCamelCase					(					lowerCAmelCase__				):
				if collection != sorted(lowerCAmelCase__				):
								raise ValueError('Collection must be ascending sorted'				)
				return True


if __name__ == "__main__":
					import sys
					SCREAMING_SNAKE_CASE						:						str					   =       0
					if debug == 1:
										SCREAMING_SNAKE_CASE						:						List[Any]					   =       [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''')
										SCREAMING_SNAKE_CASE						:						Union[str, Any]					   =       67

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










"""simple docstring"""






from ..utils import DummyObject, requires_backends





class       snake_case_       (    metaclass=_lowerCamelCase       ):



	"""simple docstring"""

	SCREAMING_SNAKE_CASE_:							List[str]   			=					["""note_seq"""]


	def __init__(      self  ,					*__a  ,					**__a						):


					"""simple docstring"""

					requires_backends(self  ,					['note_seq']						)


	@classmethod
	def       _UpperCAmelCase						(      cls  ,					*__a  ,					**__a						):


					"""simple docstring"""

					requires_backends(cls  ,					['note_seq']						)






	@classmethod
	def       _UpperCAmelCase						(      cls  ,					*__a  ,					**__a						):


					"""simple docstring"""

					requires_backends(cls  ,					['note_seq']						)


