"""simple docstring"""

import functools
from math import sqrt
from time import time


def    lowerCAmelCase			(__UpperCamelCase							:    int							,					*__UpperCamelCase							:    Optional[int]							,					**__UpperCamelCase							:    Union[str, Any]			):
							"""simple docstring"""


							__UpperCamelCase							=time()
							__UpperCamelCase							=func(*__UpperCamelCase							,					**__UpperCamelCase			)
							__UpperCamelCase							=time()
							if int(end - start			) > 0:
														print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""			)
							else:
														print(F"""{func.__name__} runtime: {(end - start) * 1_0_0_0:0.4f} ms"""			)
							return output


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


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


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


							def fib_recursive_term(__UpperCamelCase							:    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    lowerCAmelCase			(__UpperCamelCase							:    int			):
							"""simple docstring"""


							@functools.cache
							def fib_recursive_term(__UpperCamelCase							:    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    lowerCAmelCase			(__UpperCamelCase							:    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.
							__UpperCamelCase							={0: 0, 1: 1, 2: 1}  # Prefilled cache

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

														__UpperCamelCase							=rec_fn_memoized(num - 1			) + rec_fn_memoized(num - 2			)
														__UpperCamelCase							=value
														return value

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


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


							if n < 0:
														raise Exception('''n is negative'''			)
							if n >= 1_4_7_5:
														raise Exception('''n is too large'''			)
							__UpperCamelCase							=sqrt(5			)
							__UpperCamelCase							=(1 + sqrt_a) / 2
							return [round(phi**i / sqrt_a			) for i in range(n + 1			)]


if __name__ == "__main__":
				__lowercase    =				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}''')



