


'''simple docstring'''


from __future__ import annotations







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				if len(a__	) == 0:
								return False
				_SCREAMING_SNAKE_CASE					:			Optional[Any]							= len(a__	) // 2
				if a_list[midpoint] == item:
								return True
				if item < a_list[midpoint]:
								return binary_search(a_list[:midpoint]				, a__	)
				else:
								return binary_search(a_list[midpoint + 1 :]				, a__	)


if __name__ == "__main__":
				UpperCAmelCase_						:  List[str]				  =						input('Enter numbers separated by comma:\n').strip()
				UpperCAmelCase_						:  List[str]				  =						[int(item.strip()) for item in user_input.split(',')]
				UpperCAmelCase_						:  List[Any]				  =						int(input('Enter the number to be found in the list:\n').strip())
				UpperCAmelCase_						:  List[Any]				  =						'''''' if binary_search(sequence, target) else '''not '''
				print(F"{target} was {not_str}found in {sequence}")








from typing import Any

def 			lowerCAmelCase__					(     a__:						list     ,    a__:						list     ,    a__:						dict     ,    a__:						dict     ,    a__:						dict     ,    )    ->						list:


							'''simple docstring'''





							_validation(
							    a__     ,    a__     ,    a__     ,    a__     ,    a__     ,    )
							# Creates data structures and fill initial step
							_UpperCAmelCase											=     {}
							_UpperCAmelCase											=     {}
							for state in states_space:
														_UpperCAmelCase											=     observations_space[0]
														_UpperCAmelCase											=     (
														    initial_probabilities[state] * emission_probabilities[state][observation]
														)
														_UpperCAmelCase											=     None

							# Fills the data structure with the probabilities of
							# different transitions and pointers to previous states
							for o in range(1     ,    len(a__			)			):
														_UpperCAmelCase											=     observations_space[o]
														_UpperCAmelCase											=     observations_space[o - 1]
														for state in states_space:
																					# Calculates the argmax for probability function
																					_UpperCAmelCase											=     ''
																					_UpperCAmelCase											=     -1
																					for k_state in states_space:
																												_UpperCAmelCase											=     (
																												    probabilities[(k_state, prior_observation)]
																												    * transition_probabilities[k_state][state]
																												    * emission_probabilities[state][observation]
																												)
																												if probability > max_probability:
																																			_UpperCAmelCase											=     probability
																																			_UpperCAmelCase											=     k_state

            # Update probabilities and pointers dicts
																					_UpperCAmelCase											=     (
																					    probabilities[(arg_max, prior_observation)]
																					    * transition_probabilities[arg_max][state]
																					    * emission_probabilities[state][observation]
																					)

																					_UpperCAmelCase											=     arg_max

    # The final observation
							_UpperCAmelCase											=     observations_space[len(a__			) - 1]

							# argmax for given final observation
							_UpperCAmelCase											=     ''
							_UpperCAmelCase											=     -1
							for k_state in states_space:
														_UpperCAmelCase											=     probabilities[(k_state, final_observation)]
														if probability > max_probability:
																					_UpperCAmelCase											=     probability
																					_UpperCAmelCase											=     k_state
							_UpperCAmelCase											=     arg_max

							# Process pointers backwards
							_UpperCAmelCase											=     last_state
							_UpperCAmelCase											=     []
							for o in range(len(a__			) - 1     ,    -1     ,    -1			):
														result.append(a__			)
														_UpperCAmelCase											=     pointers[previous, observations_space[o]]
							result.reverse()

							return result

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    )    ->						None:


							'''simple docstring'''





							_validate_not_empty(
							    a__     ,    a__     ,    a__     ,    a__     ,    a__     ,    )
							_validate_lists(a__     ,    a__			)
							_validate_dicts(
							    a__     ,    a__     ,    a__			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    )    ->						None:


							'''simple docstring'''





							if not all(
							    [
							        observations_space,
							        states_space,
							        initial_probabilities,
							        transition_probabilities,
							        emission_probabilities,
							    ]			):
														raise ValueError('There\'s an empty parameter'			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						Any			)    ->						None:


							'''simple docstring'''





							_validate_list(a__     ,    'observations_space'			)
							_validate_list(a__     ,    'states_space'			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						str			)    ->						None:


							'''simple docstring'''





							if not isinstance(_object     ,    a__			):
														_UpperCAmelCase											=     F'''{var_name} must be a list'''
														raise ValueError(a__			)
							else:
														for x in _object:
																					if not isinstance(a__     ,    a__			):
																												_UpperCAmelCase											=     F'''{var_name} must be a list of strings'''
																												raise ValueError(a__			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						Any     ,    a__:						Any     ,    )    ->						None:


							'''simple docstring'''





							_validate_dict(a__     ,    'initial_probabilities'     ,    a__			)
							_validate_nested_dict(a__     ,    'transition_probabilities'			)
							_validate_nested_dict(a__     ,    'emission_probabilities'			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						str			)    ->						None:


							'''simple docstring'''





							_validate_dict(_object     ,    a__     ,    a__			)
							for x in _object.values():
														_validate_dict(a__     ,    a__     ,    a__     ,    a__			)

def 			lowerCAmelCase__					(     a__:						Any     ,    a__:						str     ,    a__:						type     ,    a__:						bool = False			)    ->						None:


							'''simple docstring'''





							if not isinstance(_object     ,    a__			):
														_UpperCAmelCase											=     F'''{var_name} must be a dict'''
														raise ValueError(a__			)
							if not all(isinstance(a__     ,    a__			) for x in _object			):
														_UpperCAmelCase											=     F'''{var_name} all keys must be strings'''
														raise ValueError(a__			)
							if not all(isinstance(a__     ,    a__			) for x in _object.values()			):
														_UpperCAmelCase											=     'nested dictionary ' if nested else ''
														_UpperCAmelCase											=     F'''{var_name} {nested_text}all values must be {value_type.__name__}'''
														raise ValueError(a__			)


if __name__ == "__main__":
		from doctest import testmod

		testmod()
