





"""simple docstring"""





from timeit import timeit

lowercase__					:Optional[Any]					 =							{
    'MALAYALAM': True,
    'String': False,
    'rotor': True,
    'level': True,
    'A': True,
    'BB': True,
    'ABC': False,
    'amanaplanacanalpanama': True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())


def    lowerCamelCase_							( UpperCAmelCase_	)    ->bool:





  """simple docstring"""


  __UpperCAmelCase     :    Any							=    0
  __UpperCAmelCase     :    Tuple							=    len(SCREAMING_SNAKE_CASE_	) - 1
  while start_i < end_i:
    if s[start_i] == s[end_i]:
      start_i += 1
      end_i -= 1
    else:
      return False
  return True


def    lowerCamelCase_							( UpperCAmelCase_	)    ->bool:





  """simple docstring"""


  __UpperCAmelCase     :    List[str]							=    len(SCREAMING_SNAKE_CASE_	) // 2
  __UpperCAmelCase     :    str							=    len(SCREAMING_SNAKE_CASE_	)

  # We need to traverse till half of the length of string
  # as we can get access of the i'th last element from
  # i'th index.
  # eg: [0,1,2,3,4,5] => 4th index can be accessed
  # with the help of 1st index (i==n-i-1)
  # where n is length of string
  return all(s[i] == s[n - i - 1] for i in range(SCREAMING_SNAKE_CASE_	)	)


def    lowerCamelCase_							( UpperCAmelCase_	)    ->bool:





  """simple docstring"""


  if len(SCREAMING_SNAKE_CASE_	) <= 2:
    return True
  if s[0] == s[len(SCREAMING_SNAKE_CASE_	) - 1]:
    return is_palindrome_recursive(s[1:-1]	)
  else:
    return False


def    lowerCamelCase_							( UpperCAmelCase_	)    ->bool:





  """simple docstring"""


  return s == s[::-1]


def    lowerCamelCase_							( UpperCAmelCase_	)    ->None:





  """simple docstring"""


  __UpperCAmelCase     :    List[Any]							=    f'''all({name}(key) is value for key, value in test_data.items())'''
  __UpperCAmelCase     :    Any							=    f'''from __main__ import test_data, {name}'''
  __UpperCAmelCase     :    str							=    50_00_00
  __UpperCAmelCase     :    Any							=    timeit(stmt=SCREAMING_SNAKE_CASE_	,      setup=SCREAMING_SNAKE_CASE_	,      number=SCREAMING_SNAKE_CASE_	)
  print(f'''{name:<35} finished {number:,} runs in {result:.5f} seconds'''	)


if __name__ == "__main__":
  for key, value in test_data.items():
    assert is_palindrome(key) is is_palindrome_recursive(key)
    assert is_palindrome(key) is is_palindrome_slice(key)
    print(f"""{key:21} {value}""")
  print('a man a plan a canal panama')

  # finished 500,000 runs in 0.46793 seconds
  benchmark_function('is_palindrome_slice')
  # finished 500,000 runs in 0.85234 seconds
  benchmark_function('is_palindrome')
  # finished 500,000 runs in 1.32028 seconds
  benchmark_function('is_palindrome_recursive')
  # finished 500,000 runs in 2.08679 seconds
  benchmark_function('is_palindrome_traversal')
'''simple docstring'''


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.
__snake_case						  =		10

def   A_      (       SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)			->int:
  for i in range(SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						):
    if array[i] == target:
      return i
  return -1

def   A_      (       SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)			->int:
  lowercase_     =       0
  lowercase_     =       len(SCREAMING_SNAKE_CASE_						)
  while left <= right:
    if right - left < precision:
      return lin_search(SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)

    lowercase_     =       (left + right) // 3 + 1
    lowercase_     =       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]:
      lowercase_     =       one_third - 1
    elif array[two_third] < target:
      lowercase_     =       two_third + 1

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

def   A_      (       SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)			->int:
  if left < right:
    if right - left < precision:
      return lin_search(SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)
    lowercase_     =       (left + right) // 3 + 1
    lowercase_     =       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(SCREAMING_SNAKE_CASE_ ,	one_third - 1 ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)
    elif array[two_third] < target:
      return rec_ternary_search(two_third + 1 ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)
    else:
      return rec_ternary_search(one_third + 1 ,	two_third - 1 ,	SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)
  else:
    return -1


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       __snake_case						  =		input("""Enter numbers separated by comma:\n""").strip()
       __snake_case						  =		[int(item.strip()) for item in user_input.split(""",""")]
       assert collection == sorted(collection), f"List must be ordered.\n{collection}."
       __snake_case						  =		int(input("""Enter the number to be found in the list:\n""").strip())
       __snake_case						  =		ite_ternary_search(collection, target)
       __snake_case						  =		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""")

