


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







			__lowercase 					=   0
			__lowercase 					=   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

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

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


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







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

			__lowercase 					=   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 		lowercase_  (     _UpperCamelCase  ):


			'''simple docstring'''







			if collection != sorted(_UpperCamelCase  ):
						raise ValueError('''Collection must be ascending sorted'''  )
			return True


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

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






from __future__ import annotations

import typing
from collections.abc import Iterable

import numpy as np

a : Optional[int]		=				typing.Union[Iterable[float], Iterable[int], np.ndarray]  # noqa: UP007
a : Union[str, Any]		=				typing.Union[np.floataa, int, float]  # noqa: UP007


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







			return np.sqrt(np.sum((np.asarray(_UpperCamelCase  ) - np.asarray(_UpperCamelCase  )) ** 2  )  )


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







			return sum((va - va) ** 2 for va, va in zip(_UpperCamelCase       ,			_UpperCamelCase  )  ) ** (1 / 2)


if __name__ == "__main__":


	def 		lowercase_  (     ):


				'''simple docstring'''







				from timeit import timeit

				print('''Without Numpy'''  )
				print(
				    timeit(
				        '''euclidean_distance_no_np([1, 2, 3], [4, 5, 6])'''       ,			number=1_00_00       ,			globals=globals()       ,			)  )
				print('''With Numpy'''  )
				print(
				    timeit(
				        '''euclidean_distance([1, 2, 3], [4, 5, 6])'''       ,			number=1_00_00       ,			globals=globals()       ,			)  )





	benchmark()


