



def 			lowerCAmelCase__	(					lowerCamelCase_	:	Dict ,lowerCamelCase_	:	str):





				'''simple docstring'''

				lowerCAmelCase__  :       int				=  0
				lowerCAmelCase__  :       Dict				=  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

								lowerCAmelCase__  :       Union[str, 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

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






def 			lowerCAmelCase__	(					lowerCamelCase_	:	Optional[Any] ,lowerCamelCase_	:	List[str] ,lowerCamelCase_	:	Union[str, Any] ,lowerCamelCase_	:	str):





				'''simple docstring'''

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

				lowerCAmelCase__  :       str				=  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 			lowerCAmelCase__	(					lowerCamelCase_	:	Union[str, Any]):





				'''simple docstring'''

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


if __name__ == "__main__":
			import sys
			__snake_case       :	int            =0
			if debug == 1:
						__snake_case       :	Any            =[1_0, 3_0, 4_0, 4_5, 5_0, 6_6, 7_7, 9_3]
						try:
									__assert_sorted(collection)
						except ValueError:
									sys.exit('Sequence must be ascending sorted to apply interpolation search')
						__snake_case       :	Union[str, Any]            =6_7

			__snake_case       :	Union[str, Any]            =interpolation_search(collection, target)
			if result is not None:
						print(f"""{target} found at positions: {result}""")
			else:
						print('Not found')






from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

__snake_case       :	Optional[int]            =(3, 9, -1_1, 0, 7, 5, 1, -1)
__snake_case       :	str            =(4, 6, 2, 0, 8, 1_0, 3, -2)



@dataclass
class  lowerCamelCase__    :




		'''simple docstring'''



		snake_case_			=42
		snake_case_			=42



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self	,__lowerCamelCase				)  ->    None:

						"""simple docstring"""






						lowerCAmelCase__  :       Node | None				=  None
						for i in sorted(__lowerCamelCase	,reverse=__lowerCamelCase				):
										lowerCAmelCase__  :       Dict				=  Node(__lowerCamelCase	,self.head				)



		def __iter__(self				)  ->    Iterator[int]:

						"""simple docstring"""






						lowerCAmelCase__  :       Optional[Any]				=  self.head
						while node:
										yield node.data
										lowerCAmelCase__  :       Dict				=  node.next_node



		def __len__(self				)  ->    int:

						"""simple docstring"""






						return sum(1 for _ in self				)



		def __str__(self				)  ->    str:

						"""simple docstring"""






						return " -> ".join([str(__lowerCamelCase				) for node in self]				)






def 			lowerCAmelCase__	(					lowerCamelCase_	:	SortedLinkedList ,lowerCamelCase_	:	SortedLinkedList):





				'''simple docstring'''

				return SortedLinkedList(list(lowerCamelCase_) + list(lowerCamelCase_))


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							__snake_case       :	Any            =SortedLinkedList
							print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))

