




from __future__ import annotations







def 			lowerCamelCase_		(       UpperCamelCase__				:      str ,     UpperCamelCase__				:      list[str] | None = None ,     UpperCamelCase__				:      dict[str, float] | None = None ,     UpperCamelCase__				:      bool = False ,     )     ->       tuple[int, float, str]:





				"""simple docstring"""


				__lowerCamelCase		       =    cipher_alphabet or [chr(UpperCamelCase__      ) for i in range(97 ,     123      )]

				# If the argument is None or the user provided an empty dictionary
				if not frequencies_dict:
								# Frequencies of letters in the english language (how much they show up)
								__lowerCamelCase		       =    {
								    'a': 0.0_84_97,
								    'b': 0.0_14_92,
								    'c': 0.0_22_02,
								    'd': 0.0_42_53,
								    'e': 0.1_11_62,
								    'f': 0.0_22_28,
								    'g': 0.0_20_15,
								    'h': 0.0_60_94,
								    'i': 0.0_75_46,
								    'j': 0.0_01_53,
								    'k': 0.0_12_92,
								    'l': 0.0_40_25,
								    'm': 0.0_24_06,
								    'n': 0.0_67_49,
								    'o': 0.0_75_07,
								    'p': 0.0_19_29,
								    'q': 0.0_00_95,
								    'r': 0.0_75_87,
								    's': 0.0_63_27,
								    't': 0.0_93_56,
								    'u': 0.0_27_58,
								    'v': 0.0_09_78,
								    'w': 0.0_25_60,
								    'x': 0.0_01_50,
								    'y': 0.0_19_94,
								    'z': 0.0_00_77,
								}
				else:
								# Custom frequencies dictionary
								__lowerCamelCase		       =    frequencies_dict

				if not case_sensitive:
								__lowerCamelCase		       =    ciphertext.lower()

				# Chi squared statistic values
				__lowerCamelCase		       =    {}

				# cycle through all of the shifts
				for shift in range(len(UpperCamelCase__      )      ):
								__lowerCamelCase		       =    ''

								# decrypt the message with the shift
								for letter in ciphertext:
												try:
																# Try to index the letter in the alphabet
																__lowerCamelCase		       =    (alphabet_letters.index(letter.lower()      ) - shift) % len(
																    UpperCamelCase__      )
																decrypted_with_shift += (
																    alphabet_letters[new_key].upper()
																    if case_sensitive and letter.isupper()
																    else alphabet_letters[new_key]
																)
												except ValueError:
																# Append the character if it isn't in the alphabet
																decrypted_with_shift += letter

								__lowerCamelCase		       =    0.0

								# Loop through each letter in the decoded message with the shift
								for letter in decrypted_with_shift:
												if case_sensitive:
																__lowerCamelCase		       =    letter.lower()
																if letter in frequencies:
																				# Get the amount of times the letter occurs in the message
																				__lowerCamelCase		       =    decrypted_with_shift.lower().count(UpperCamelCase__      )

																				# Get the excepcted amount of times the letter should appear based
																				# on letter frequencies
																				__lowerCamelCase		       =    frequencies[letter] * occurrences

																				# Complete the chi squared statistic formula
																				__lowerCamelCase		       =    ((occurrences - expected) ** 2) / expected

																				# Add the margin of error to the total chi squared statistic
																				chi_squared_statistic += chi_letter_value
												else:
																if letter.lower() in frequencies:
																				# Get the amount of times the letter occurs in the message
																				__lowerCamelCase		       =    decrypted_with_shift.count(UpperCamelCase__      )

																				# Get the excepcted amount of times the letter should appear based
																				# on letter frequencies
																				__lowerCamelCase		       =    frequencies[letter] * occurrences

																				# Complete the chi squared statistic formula
																				__lowerCamelCase		       =    ((occurrences - expected) ** 2) / expected

																				# Add the margin of error to the total chi squared statistic
																				chi_squared_statistic += chi_letter_value

        # Add the data to the chi_squared_statistic_values dictionary
								__lowerCamelCase		       =    (
								    chi_squared_statistic,
								    decrypted_with_shift,
								)

				# Get the most likely cipher by finding the cipher with the smallest chi squared
				# statistic
				def chi_squared_statistic_values_sorting_key(UpperCamelCase__				:      int      ) -> tuple[float, str]:
								return chi_squared_statistic_values[key]

				__lowerCamelCase		       =    min(
				    UpperCamelCase__ ,     key=UpperCamelCase__ ,     )

				# Get all the data from the most likely cipher (key, decoded message)
				(
				    (
				    __lowerCamelCase
				)       ,						(
				    __lowerCamelCase
				)       ,						
				)		       =    chi_squared_statistic_values[most_likely_cipher]

				# Return the data on the most likely shift
				return (
				    most_likely_cipher,
				    most_likely_cipher_chi_squared_value,
				    decoded_most_likely_cipher,
				)








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")


