

'''simple docstring'''







from __future__ import annotations
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     bool:
       if len(UpperCAmelCase__			) == 0:
              return False
       A_		   = len(UpperCAmelCase__			) // 2
       if a_list[midpoint] == item:
              return True
       if item < a_list[midpoint]:
              return binary_search(a_list[:midpoint],    UpperCAmelCase__			)
       else:
              return binary_search(a_list[midpoint + 1 :],    UpperCAmelCase__			)


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



'''simple docstring'''







def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     bool:
       A_		   = len(UpperCAmelCase__			)
       A_		   = [[False] * (required_sum + 1) for _ in range(arr_len + 1			)]

       # for each arr value, a sum of zero(0) can be formed by not taking any element
       # hence True/1
       for i in range(arr_len + 1			):
              A_		   = True

       # sum is not zero and set is empty then false
       for i in range(1,    required_sum + 1			):
              A_		   = False

       for i in range(1,    arr_len + 1			):
              for j in range(1,    required_sum + 1			):
                     if arr[i - 1] > j:
                            A_		   = subset[i - 1][j]
                     if arr[i - 1] <= j:
                            A_		   = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

       return subset[arr_len][required_sum]


if __name__ == "__main__":
      import doctest

      doctest.testmod()
