"""simple docstring"""







import functools
from math import sqrt
from time import time




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int  ,       *_SCREAMING_SNAKE_CASE				:				Optional[int]  ,       **_SCREAMING_SNAKE_CASE				:				Union[str, Any]						)    ->     Optional[Any]:







     '''simple docstring'''


     __A					:					Dict								=		time()
     __A					:					Any								=		func(*__UpperCamelCase  ,       **__UpperCamelCase						)
     __A					:					Union[str, Any]								=		time()
     if int(end - start						) > 0:
          print(F'{func.__name__} runtime: {(end - start):0.4f} s'						)
     else:
          print(F'{func.__name__} runtime: {(end - start) * 1000:0.4f} ms'						)
     return output




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int						)    ->     Tuple:







     '''simple docstring'''


     if n < 0:
          raise Exception('n is negative'						)
     if n == 0:
          return [0]
     __A					:					Optional[Any]								=		[0, 1]
     for _ in range(n - 1						):
          fib.append(fib[-1] + fib[-2]						)
     return fib




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int						)    ->     Union[str, Any]:







     '''simple docstring'''


     def fib_recursive_term(_SCREAMING_SNAKE_CASE				:				int						) -> int:
          if i < 0:
               raise Exception('n is negative'						)
          if i < 2:
               return i
          return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

     if n < 0:
          raise Exception('n is negative'						)
     return [fib_recursive_term(__UpperCamelCase						) for i in range(n + 1						)]




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int						)    ->     List[Any]:







     '''simple docstring'''


     @functools.cache
     def fib_recursive_term(_SCREAMING_SNAKE_CASE				:				int						) -> int:
          if i < 0:
               raise Exception('n is negative'						)
          if i < 2:
               return i
          return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

     if n < 0:
          raise Exception('n is negative'						)
     return [fib_recursive_term(__UpperCamelCase						) for i in range(n + 1						)]




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int						)    ->     int:







     '''simple docstring'''


     if n < 0:
          raise Exception('n is negative'						)
     # Cache must be outside recursuive function
     # other it will reset every time it calls itself.
     __A					:					Tuple								=		{0: 0, 1: 1, 2: 1}  # Prefilled cache

     def rec_fn_memoized(_SCREAMING_SNAKE_CASE				:				int						) -> int:
          if num in cache:
               return cache[num]

          __A					:					Dict								=		rec_fn_memoized(num - 1						) + rec_fn_memoized(num - 2						)
          __A					:					Tuple								=		value
          return value

     return [rec_fn_memoized(__UpperCamelCase						) for i in range(n + 1						)]




def 						_lowercase				(  _SCREAMING_SNAKE_CASE				:				int						)    ->     Optional[Any]:







     '''simple docstring'''


     if n < 0:
          raise Exception('n is negative'						)
     if n >= 1475:
          raise Exception('n is too large'						)
     __A					:					List[Any]								=		sqrt(5						)
     __A					:					Union[str, Any]								=		(1 + sqrt_a) / 2
     return [round(phi**i / sqrt_a						) for i in range(n + 1						)]


if __name__ == "__main__":
       lowerCamelCase      : Optional[int]       =30
       time_func(fib_iterative, num)
       time_func(fib_recursive, num)  # Around 3s runtime
       time_func(fib_recursive_cached, num)  # Around 0ms runtime
       time_func(fib_memoization, num)
       time_func(fib_binet, num)




"""simple docstring"""

def    lowerCAmelCase			(__UpperCamelCase							:    list							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


							for index, item in enumerate(__UpperCamelCase			):
														if item == target:
																					return index
							return -1


def    lowerCAmelCase			(__UpperCamelCase							:    list							,					__UpperCamelCase							:    int							,					__UpperCamelCase							:    int							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


							if not (0 <= high < len(__UpperCamelCase			) and 0 <= low < len(__UpperCamelCase			)):
														raise Exception('''Invalid upper or lower bound!'''			)
							if high < low:
														return -1
							if sequence[low] == target:
														return low
							if sequence[high] == target:
														return high
							return rec_linear_search(__UpperCamelCase							,					low + 1							,					high - 1							,					__UpperCamelCase			)


if __name__ == "__main__":
				__lowercase    =				input('''Enter numbers separated by comma:\n''').strip()
				__lowercase    =				[int(item.strip()) for item in user_input.split(''',''')]

				__lowercase    =				int(input('''Enter a single number to be found in the list:\n''').strip())
				__lowercase    =				linear_search(sequence, target)
				if result != -1:
								print(f'''linear_search({sequence}, {target}) = {result}''')
				else:
								print(f'''{target} was not found in {sequence}''')



