
"""simple docstring"""






class 			_SCREAMING_SNAKE_CASE					:






			def __init__(					self       )			->     int:
						lowerCAmelCase_    :List[str]			     =  """"""
						lowerCAmelCase_    :List[Any]			     =  """"""
						lowerCAmelCase_    :Union[str, Any]			     =  []






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						if m == -1:
									return n + 1
						elif n == -1:
									return m + 1
						elif self.dp[m][n] > -1:
									return self.dp[m][n]
						else:
									if self.worda[m] == self.worda[n]:
												lowerCAmelCase_    :List[Any]			     =  self.__min_dist_top_down_dp(m - 1       ,   n - 1       )
									else:
												lowerCAmelCase_    :int			     =  self.__min_dist_top_down_dp(__A       ,   n - 1       )
												lowerCAmelCase_    :Dict			     =  self.__min_dist_top_down_dp(m - 1       ,   __A       )
												lowerCAmelCase_    :Optional[int]			     =  self.__min_dist_top_down_dp(m - 1       ,   n - 1       )
												lowerCAmelCase_    :Tuple			     =  1 + min(__A       ,   __A       ,   __A       )

									return self.dp[m][n]






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						lowerCAmelCase_    :List[str]			     =  worda
						lowerCAmelCase_    :int			     =  worda
						lowerCAmelCase_    :int			     =  [[-1 for _ in range(len(__A       )       )] for _ in range(len(__A       )       )]

						return self.__min_dist_top_down_dp(len(__A       ) - 1       ,   len(__A       ) - 1       )






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						lowerCAmelCase_    :Optional[Any]			     =  worda
						lowerCAmelCase_    :Dict			     =  worda
						lowerCAmelCase_    :str			     =  len(__A       )
						lowerCAmelCase_    :Union[str, Any]			     =  len(__A       )
						lowerCAmelCase_    :List[str]			     =  [[0 for _ in range(n + 1       )] for _ in range(m + 1       )]

						for i in range(m + 1       ):
									for j in range(n + 1       ):
												if i == 0:  # first string is empty
															lowerCAmelCase_    :int			     =  j
												elif j == 0:  # second string is empty
															lowerCAmelCase_    :int			     =  i
												elif worda[i - 1] == worda[j - 1]:  # last characters are equal
															lowerCAmelCase_    :Union[str, Any]			     =  self.dp[i - 1][j - 1]
												else:
															lowerCAmelCase_    :Union[str, Any]			     =  self.dp[i][j - 1]
															lowerCAmelCase_    :Tuple			     =  self.dp[i - 1][j]
															lowerCAmelCase_    :Dict			     =  self.dp[i - 1][j - 1]
															lowerCAmelCase_    :Tuple			     =  1 + min(__A       ,   __A       ,   __A       )
						return self.dp[m][n]


if __name__ == "__main__":
				__UpperCAmelCase       =  EditDistance()

				print('****************** Testing Edit Distance DP Algorithm ******************')
				print()

				__UpperCAmelCase       =  input('Enter the first string: ').strip()
				__UpperCAmelCase       =  input('Enter the second string: ').strip()

				print()
				print(F"""The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}""")
				print(F"""The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}""")
				print()
				print('*************** End of Testing Edit Distance DP Algorithm ***************')












from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
__A        =    10







def 			lowerCamelCase_		(       UpperCamelCase__				:      int ,     UpperCamelCase__				:      int ,     UpperCamelCase__				:      list[int] ,     UpperCamelCase__				:      int      )     ->       int:





				"""simple docstring"""


				for i in range(UpperCamelCase__ ,     UpperCamelCase__      ):
								if array[i] == target:
												return i
				return -1







def 			lowerCamelCase_		(       UpperCamelCase__				:      list[int] ,     UpperCamelCase__				:      int      )     ->       int:





				"""simple docstring"""


				__lowerCamelCase		       =    0
				__lowerCamelCase		       =    len(UpperCamelCase__      )
				while left <= right:
								if right - left < precision:
												return lin_search(UpperCamelCase__ ,     UpperCamelCase__ ,     UpperCamelCase__ ,     UpperCamelCase__      )

								__lowerCamelCase		       =    (left + right) // 3 + 1
								__lowerCamelCase		       =    2 * (left + right) // 3 + 1

								if array[one_third] == target:
												return one_third
								elif array[two_third] == target:
												return two_third

								elif target < array[one_third]:
												__lowerCamelCase		       =    one_third - 1
								elif array[two_third] < target:
												__lowerCamelCase		       =    two_third + 1

								else:
												__lowerCamelCase		       =    one_third + 1
												__lowerCamelCase		       =    two_third - 1
				else:
								return -1







def 			lowerCamelCase_		(       UpperCamelCase__				:      int ,     UpperCamelCase__				:      int ,     UpperCamelCase__				:      list[int] ,     UpperCamelCase__				:      int      )     ->       int:





				"""simple docstring"""


				if left < right:
								if right - left < precision:
												return lin_search(UpperCamelCase__ ,     UpperCamelCase__ ,     UpperCamelCase__ ,     UpperCamelCase__      )
								__lowerCamelCase		       =    (left + right) // 3 + 1
								__lowerCamelCase		       =    2 * (left + right) // 3 + 1

								if array[one_third] == target:
												return one_third
								elif array[two_third] == target:
												return two_third

								elif target < array[one_third]:
												return rec_ternary_search(UpperCamelCase__ ,     one_third - 1 ,     UpperCamelCase__ ,     UpperCamelCase__      )
								elif array[two_third] < target:
												return rec_ternary_search(two_third + 1 ,     UpperCamelCase__ ,     UpperCamelCase__ ,     UpperCamelCase__      )
								else:
												return rec_ternary_search(one_third + 1 ,     two_third - 1 ,     UpperCamelCase__ ,     UpperCamelCase__      )
				else:
								return -1


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					__A        =    input("Enter numbers separated by comma:\n").strip()
					__A        =    [int(item.strip()) for item in user_input.split(",")]
					assert collection == sorted(collection), f"List must be ordered.\n{collection}."
					__A        =    int(input("Enter the number to be found in the list:\n").strip())
					__A        =    ite_ternary_search(collection, target)
					__A        =    rec_ternary_search(0, len(collection) - 1, collection, target)
					if resulta != -1:
										print(f'''Iterative search: {target} found at positions: {resulta}''')
										print(f'''Recursive search: {target} found at positions: {resulta}''')
					else:
										print("Not found")


