





def   lowerCamelCase__       (       UpperCamelCase__     :    Optional[int]    ,      UpperCamelCase__     :    str  )     ->	int:



					'''simple docstring'''




					_snake_case													=			0
					_snake_case													=			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													=			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													=			sorted_collection[point]
										if current_item == item:
															return point
										else:
															if point < left:
																				_snake_case													=			left
																				_snake_case													=			point
															elif point > right:
																				_snake_case													=			right
																				_snake_case													=			point
															else:
																				if item < current_item:
																									_snake_case													=			point - 1
																				else:
																									_snake_case													=			point + 1
					return None





def   lowerCamelCase__       (       UpperCamelCase__     :    Any    ,      UpperCamelCase__     :    Optional[int]    ,      UpperCamelCase__     :    Optional[int]    ,      UpperCamelCase__     :    int  )     ->	Dict:



					'''simple docstring'''




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

					_snake_case													=			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__       (       UpperCamelCase__     :    Optional[int]  )     ->	Optional[int]:



					'''simple docstring'''




					if collection != sorted(UpperCamelCase__  ):
										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""")










def   lowerCamelCase__       (       UpperCamelCase__     :    Tuple    ,      UpperCamelCase__     :    Optional[int]  )     ->	Tuple:



					'''simple docstring'''




					_snake_case													=			[0 for i in range(r + 1  )]
					# nc0 = 1
					_snake_case													=			1
					for i in range(1    ,      n + 1  ):
										# to compute current row from previous row.
										_snake_case													=			min(UpperCamelCase__    ,      UpperCamelCase__  )
										while j > 0:
															c[j] += c[j - 1]
															j -= 1
					return c[r]




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



