

'''simple docstring'''





def 							_lowerCAmelCase (      __magic_name__	:    str      ,   __magic_name__	:    Dict	)							->     List[Any]:
						lowercase   :       str								=0
						lowercase   :       int								=len(_SCREAMING_SNAKE_CASE	) - 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

												lowercase   :       List[Any]								=left + ((item - sorted_collection[left]) * (right - left)) // (
												    sorted_collection[right] - sorted_collection[left]
												)

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

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






def 							_lowerCAmelCase (      __magic_name__	:    Dict      ,   __magic_name__	:    int      ,   __magic_name__	:    List[Any]      ,   __magic_name__	:    List[str]	)							->     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

						lowercase   :       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(_SCREAMING_SNAKE_CASE	):
												return None

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






def 							_lowerCAmelCase (      __magic_name__	:    int	)							->     Optional[Any]:
						if collection != sorted(_SCREAMING_SNAKE_CASE	):
												raise ValueError('''Collection must be ascending sorted'''	)
						return True


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

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








'''simple docstring'''





def 							_lowerCAmelCase (      __magic_name__	:    int      ,   __magic_name__	:    Optional[Any]	)							->     str:
						lowercase   :       Optional[Any]								=[0 for i in range(r + 1	)]
						# nc0 = 1
						lowercase   :       Optional[Any]								=1
						for i in range(1      ,   n + 1	):
												# to compute current row from previous row.
												lowercase   :       str								=min(__magic_name__      ,   __magic_name__	)
												while j > 0:
																		c[j] += c[j - 1]
																		j -= 1
						return c[r]







print(binomial_coefficient(n=10, r=5))





