


def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Dict       ,  SCREAMING_SNAKE_CASE_   :		Any	):





			"""simple docstring"""




			UpperCamelCase         =					0
			UpperCamelCase         =					len(SCREAMING_SNAKE_CASE_	) - 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         =					left + ((item - sorted_collection[left]) * (right - left)) // (
						    sorted_collection[right] - sorted_collection[left]
						)

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

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






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		str       ,  SCREAMING_SNAKE_CASE_   :		List[str]       ,  SCREAMING_SNAKE_CASE_   :		Optional[Any]       ,  SCREAMING_SNAKE_CASE_   :		Optional[int]	):





			"""simple docstring"""




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

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

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

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






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		str	):





			"""simple docstring"""




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


if __name__ == "__main__":
			import sys
			__snake_case            =   0
			if debug == 1:
						__snake_case            =   [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")
						__snake_case            =   67

			__snake_case            =   interpolation_search(collection, target)
			if result is not None:
						print(F'''{target} found at positions: {result}''')
			else:
						print("Not found")



import math
import unittest






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			assert isinstance(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_	) and (
			    number >= 0
			), "'number' must been an int and positive"

			if 1 < number < 4:
						# 2 and 3 are primes
						return True
			elif number < 2 or number % 2 == 0 or number % 3 == 0:
						# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
						return False

			# All primes number are in format of 6k +/- 1
			for i in range(5       ,  int(math.sqrt(SCREAMING_SNAKE_CASE_	) + 1	)       ,  6	):
						if number % i == 0 or number % (i + 2) == 0:
									return False
			return True




class    UpperCAmelCase					(       unittest.TestCase    ):




			def   lowerCamelCase_					(						self							:		Any						):







						"""simple docstring"""







						self.assertTrue(is_prime(2						)						)
						self.assertTrue(is_prime(3						)						)
						self.assertTrue(is_prime(5						)						)
						self.assertTrue(is_prime(7						)						)
						self.assertTrue(is_prime(1_1						)						)
						self.assertTrue(is_prime(1_3						)						)
						self.assertTrue(is_prime(1_7						)						)
						self.assertTrue(is_prime(1_9						)						)
						self.assertTrue(is_prime(2_3						)						)
						self.assertTrue(is_prime(2_9						)						)





			def   lowerCamelCase_					(						self							:		Dict						):







						"""simple docstring"""







						with self.assertRaises(__magic_name__						):
									is_prime(-1_9						)
						self.assertFalse(
						    is_prime(0						)       ,       """Zero doesn't have any positive factors, primes must have exactly two."""       ,       )
						self.assertFalse(
						    is_prime(1						)       ,       """One only has 1 positive factor, primes must have exactly two."""       ,       )
						self.assertFalse(is_prime(2 * 2						)						)
						self.assertFalse(is_prime(2 * 3						)						)
						self.assertFalse(is_prime(3 * 3						)						)
						self.assertFalse(is_prime(3 * 5						)						)
						self.assertFalse(is_prime(3 * 5 * 7						)						)


if __name__ == "__main__":
			unittest.main()




