


'''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.
__lowerCamelCase												=						10


def        a__     (					UpperCamelCase_						:      List[Any],   UpperCamelCase_						:      Optional[int],   UpperCamelCase_						:      Dict,   UpperCamelCase_						:      Optional[Any]						):
   for i in range(SCREAMING_SNAKE_CASE_,   SCREAMING_SNAKE_CASE_						):
      if array[i] == target:
         return i
   return -1


def        a__     (					UpperCamelCase_						:      Union[str, Any],   UpperCamelCase_						:      int						):
   UpperCAmelCase__	:List[Any]      =      0
   UpperCAmelCase__	:List[str]      =      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_						)

      UpperCAmelCase__	:Optional[int]      =      (left + right) // 3 + 1
      UpperCAmelCase__	:str      =      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]:
         UpperCAmelCase__	:Optional[int]      =      one_third - 1
      elif array[two_third] < target:
         UpperCAmelCase__	:Union[str, Any]      =      two_third + 1

      else:
         UpperCAmelCase__	:Union[str, Any]      =      one_third + 1
         UpperCAmelCase__	:Tuple      =      two_third - 1
   else:
      return -1


def        a__     (					UpperCamelCase_						:      Optional[Any],   UpperCamelCase_						:      int,   UpperCamelCase_						:      Tuple,   UpperCamelCase_						:      List[Any]						):
   if left < right:
      if right - left < precision:
         return lin_search(SCREAMING_SNAKE_CASE_,   SCREAMING_SNAKE_CASE_,   SCREAMING_SNAKE_CASE_,   SCREAMING_SNAKE_CASE_						)
      UpperCAmelCase__	:List[Any]      =      (left + right) // 3 + 1
      UpperCAmelCase__	:Any      =      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()

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




'''simple docstring'''


def   A_      (       SCREAMING_SNAKE_CASE_						)			->bool:
  if number < 0:
    raise ValueError("""number must not be negative"""						)
  return number & (number - 1) == 0


if __name__ == "__main__":
       import doctest

       doctest.testmod()

