




from __future__ import annotations

import bisect




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int  ,			A__       :					int = 0  ,			A__       :					int = -1	):





       '''simple docstring'''



       if hi < 0:
              __lowerCamelCase   =						len(A__	)

       while lo < hi:
              __lowerCamelCase   =						lo + (hi - lo) // 2
              if sorted_collection[mid] < item:
                     __lowerCamelCase   =						mid + 1
              else:
                     __lowerCamelCase   =						mid

       return lo




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int  ,			A__       :					int = 0  ,			A__       :					int = -1	):





       '''simple docstring'''



       if hi < 0:
              __lowerCamelCase   =						len(A__	)

       while lo < hi:
              __lowerCamelCase   =						lo + (hi - lo) // 2
              if sorted_collection[mid] <= item:
                     __lowerCamelCase   =						mid + 1
              else:
                     __lowerCamelCase   =						mid

       return lo




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int  ,			A__       :					int = 0  ,			A__       :					int = -1	):





       '''simple docstring'''



       sorted_collection.insert(bisect_left(A__  ,			A__  ,			A__  ,			A__	)  ,			A__	)




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int  ,			A__       :					int = 0  ,			A__       :					int = -1	):





       '''simple docstring'''



       sorted_collection.insert(bisect_right(A__  ,			A__  ,			A__  ,			A__	)  ,			A__	)




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int	):





       '''simple docstring'''



       __lowerCamelCase   =						0
       __lowerCamelCase   =						len(A__	) - 1

       while left <= right:
              __lowerCamelCase   =						left + (right - left) // 2
              __lowerCamelCase   =						sorted_collection[midpoint]
              if current_item == item:
                     return midpoint
              elif item < current_item:
                     __lowerCamelCase   =						midpoint - 1
              else:
                     __lowerCamelCase   =						midpoint + 1
       return None




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int	):





       '''simple docstring'''



       __lowerCamelCase   =						bisect.bisect_left(A__  ,			A__	)
       if index != len(A__	) and sorted_collection[index] == item:
              return index
       return None




def 					lowerCamelCase__       (						A__       :					list[int]  ,			A__       :					int  ,			A__       :					int  ,			A__       :					int	):





       '''simple docstring'''



       if right < left:
              return None

       __lowerCamelCase   =						left + (right - left) // 2

       if sorted_collection[midpoint] == item:
              return midpoint
       elif sorted_collection[midpoint] > item:
              return binary_search_by_recursion(A__  ,			A__  ,			A__  ,			midpoint - 1	)
       else:
              return binary_search_by_recursion(A__  ,			A__  ,			midpoint + 1  ,			A__	)


if __name__ == "__main__":
       UpperCAmelCase_									=	input('Enter numbers separated by comma:\n').strip()
       UpperCAmelCase_									=	sorted(int(item) for item in user_input.split(','))
       UpperCAmelCase_									=	int(input('Enter a single number to be found in the list:\n'))
       UpperCAmelCase_									=	binary_search(collection, target)
       if result is None:
              print(f"""{target} was not found in {collection}.""")
       else:
              print(f"""{target} was found at position {result} in {collection}.""")








import functools



def 		A_				(     _lowerCAmelCase							,   _lowerCAmelCase     )						-> int:
 UpperCamelCase	:					Optional[int]       	=   len(_lowerCAmelCase     )
 UpperCamelCase	:					List[str]       	=   len(_lowerCAmelCase     )

 @functools.cache
 def min_distance(_lowerCAmelCase							,   _lowerCAmelCase     ) -> int:
  # if first word index is overflow - delete all from the second word
  if indexa >= len_worda:
   return len_worda - indexa
  # if second word index is overflow - delete all from the first word
  if indexa >= len_worda:
   return len_worda - indexa
  UpperCamelCase	:					Union[str, Any]       	=   int(worda[indexa] != worda[indexa]     )  # current letters not identical
  return min(
      1 + min_distance(indexa + 1							,   _lowerCAmelCase     )							,   1 + min_distance(_lowerCAmelCase							,   indexa + 1     )							,   diff + min_distance(indexa + 1							,   indexa + 1     )							,   )

 return min_distance(0							,   0     )


if __name__ == "__main__":
    import doctest

    doctest.testmod()
