



'''simple docstring'''






def 				snake_case_  (      _lowerCAmelCase						:		Union[str, Any]     ,   _lowerCAmelCase						:		Tuple						)   ->     Union[str, Any]:
							UpperCAmelCase				: Tuple											=	0
							UpperCAmelCase				: int											=	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

														UpperCAmelCase				: Tuple											=	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

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


def 				snake_case_  (      _lowerCAmelCase						:		List[Any]     ,   _lowerCAmelCase						:		Optional[int]     ,   _lowerCAmelCase						:		Dict     ,   _lowerCAmelCase						:		Optional[Any]						)   ->     Any:

							# avoid divided by 0 during interpolation
							if sorted_collection[left] == sorted_collection[right]:
														if sorted_collection[left] == item:
																					return left
														else:
																					return None

							UpperCAmelCase				: 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(_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 				snake_case_  (      _lowerCAmelCase						:		Dict						)   ->     int:
							if collection != sorted(_lowerCAmelCase						):
														raise ValueError('''Collection must be ascending sorted'''						)
							return True


if __name__ == "__main__":
						import sys
						UpperCamelCase__:     str										=    0
						if debug == 1:
												UpperCamelCase__:     str										=    [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__:     Dict										=    67

						UpperCamelCase__:     Optional[int]										=    interpolation_search(collection, target)
						if result is not None:
												print(F"{target} found at positions: {result}")
						else:
												print("Not found")










'''simple docstring'''






import numpy as np

UpperCamelCase__:     Any										=    [
    ["a", "b", "c", "d", "e"],
    ["f", "g", "h", "i", "k"],
    ["l", "m", "n", "o", "p"],
    ["q", "r", "s", "t", "u"],
    ["v", "w", "x", "y", "z"],
]

class        SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	def __init__(		self    :  Any	)    ->	None:
								UpperCAmelCase				: Optional[int]											=	np.array(__snake_case	)







	def   A			(		self    :  str	,    __snake_case    :  str	)    ->	np.ndarray:
								UpperCAmelCase							,	UpperCAmelCase				: Dict											=	np.where(letter == self.SQUARE	)
								UpperCAmelCase				: Dict											=	np.concatenate([indexa + 1, indexa + 1]	)
								return indexes







	def   A			(		self    :  Union[str, Any]	,    __snake_case    :  int	,    __snake_case    :  int	)    ->	str:
								UpperCAmelCase				: int											=	self.SQUARE[indexa - 1, indexa - 1]
								return letter







	def   A			(		self    :  List[Any]	,    __snake_case    :  str	)    ->	str:
								UpperCAmelCase				: Any											=	message.lower()
								UpperCAmelCase				: List[Any]											=	message.replace(''' '''	,    ''''''	)
								UpperCAmelCase				: List[Any]											=	message.replace('''j'''	,    '''i'''	)

								UpperCAmelCase				: Tuple											=	np.empty((2, len(__snake_case	))	)
								for letter_index in range(len(__snake_case	)	):
															UpperCAmelCase				: str											=	self.letter_to_numbers(message[letter_index]	)

															UpperCAmelCase				: Any											=	numbers[0]
															UpperCAmelCase				: Optional[Any]											=	numbers[1]

								UpperCAmelCase				: List[str]											=	first_step.reshape(2 * len(__snake_case	)	)
								UpperCAmelCase				: Union[str, Any]											=	''''''
								for numbers_index in range(len(__snake_case	)	):
															UpperCAmelCase				: Dict											=	int(second_step[numbers_index * 2]	)
															UpperCAmelCase				: Union[str, Any]											=	int(second_step[(numbers_index * 2) + 1]	)
															UpperCAmelCase				: Dict											=	self.numbers_to_letter(__snake_case	,    __snake_case	)
															UpperCAmelCase				: int											=	encoded_message + letter

								return encoded_message







	def   A			(		self    :  Optional[Any]	,    __snake_case    :  str	)    ->	str:
								UpperCAmelCase				: str											=	message.lower()
								message.replace(''' '''	,    ''''''	)
								UpperCAmelCase				: Optional[int]											=	np.empty(2 * len(__snake_case	)	)
								for letter_index in range(len(__snake_case	)	):
															UpperCAmelCase				: int											=	self.letter_to_numbers(message[letter_index]	)
															UpperCAmelCase				: Optional[Any]											=	numbers[0]
															UpperCAmelCase				: List[Any]											=	numbers[1]

								UpperCAmelCase				: Tuple											=	first_step.reshape((2, len(__snake_case	))	)
								UpperCAmelCase				: str											=	''''''
								for numbers_index in range(len(__snake_case	)	):
															UpperCAmelCase				: Tuple											=	int(second_step[0, numbers_index]	)
															UpperCAmelCase				: List[str]											=	int(second_step[1, numbers_index]	)
															UpperCAmelCase				: Union[str, Any]											=	self.numbers_to_letter(__snake_case	,    __snake_case	)
															UpperCAmelCase				: Union[str, Any]											=	decoded_message + letter

								return decoded_message





