


'''simple docstring'''






def    _snake_case  (	A					,       A			)		->       Tuple:
							lowerCAmelCase__			  =      0
							lowerCAmelCase__			  =      len(A			) - 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__			  =      left + ((item - sorted_collection[left]) * (right - left)) // (
														    sorted_collection[right] - sorted_collection[left]
														)

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

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


def    _snake_case  (	A					,       A					,       A					,       A			)		->       List[str]:

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

							lowerCAmelCase__			  =      left + ((item - sorted_collection[left]) * (right - left)) // (
							    sorted_collection[right] - sorted_collection[left]
							)

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

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


def    _snake_case  (	A			)		->       Dict:
							if collection != sorted(A			):
														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'''






from __future__ import annotations

from random import choice


def    _snake_case  (	A			)		->       int:
							return choice(A			)


def    _snake_case  (	A					,       A			)		->       int:
							lowerCAmelCase__			  =      random_pivot(A			)

							# partition based on pivot
							# linear time
							lowerCAmelCase__			  =      [e for e in lst if e < pivot]
							lowerCAmelCase__			  =      [e for e in lst if e > pivot]

							# if we get lucky, pivot might be the element we want.
							# we can easily see this:
							# small (elements smaller than k)
							# + pivot (kth element)
							# + big (elements larger than k)
							if len(A			) == k - 1:
														return pivot
							# pivot is in elements bigger than k
							elif len(A			) < k - 1:
														return kth_number(A					,       k - len(A			) - 1			)
							# pivot is in elements smaller than k
							else:
														return kth_number(A					,       A			)


if __name__ == "__main__":
		import doctest

		doctest.testmod()