





"""simple docstring"""





from __future__ import annotations

import bisect


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_ = 0  ,			UpperCAmelCase_ = -1  )						->int:





  """simple docstring"""


  if hi < 0:
    __UpperCAmelCase    :						Union[str, Any]       =						len(UpperCAmelCase_  )

  while lo < hi:
    __UpperCAmelCase    :						Dict       =						lo + (hi - lo) // 2
    if sorted_collection[mid] < item:
      __UpperCAmelCase    :						Tuple       =						mid + 1
    else:
      __UpperCAmelCase    :						Optional[Any]       =						mid

  return lo


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_ = 0  ,			UpperCAmelCase_ = -1  )						->int:





  """simple docstring"""


  if hi < 0:
    __UpperCAmelCase    :						List[Any]       =						len(UpperCAmelCase_  )

  while lo < hi:
    __UpperCAmelCase    :						str       =						lo + (hi - lo) // 2
    if sorted_collection[mid] <= item:
      __UpperCAmelCase    :						Optional[int]       =						mid + 1
    else:
      __UpperCAmelCase    :						Dict       =						mid

  return lo


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_ = 0  ,			UpperCAmelCase_ = -1  )						->None:





  """simple docstring"""


  sorted_collection.insert(bisect_left(UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  )  ,			UpperCAmelCase_  )


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_ = 0  ,			UpperCAmelCase_ = -1  )						->None:





  """simple docstring"""


  sorted_collection.insert(bisect_right(UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  )  ,			UpperCAmelCase_  )


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  )						->int | None:





  """simple docstring"""


  __UpperCAmelCase    :						Tuple       =						0
  __UpperCAmelCase    :						List[str]       =						len(UpperCAmelCase_  ) - 1

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


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  )						->int | None:





  """simple docstring"""


  __UpperCAmelCase    :						Any       =						bisect.bisect_left(UpperCAmelCase_  ,			UpperCAmelCase_  )
  if index != len(UpperCAmelCase_  ) and sorted_collection[index] == item:
    return index
  return None


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  ,			UpperCAmelCase_  )						->int | None:





  """simple docstring"""


  if right < left:
    return None

  __UpperCAmelCase    :						List[Any]       =						left + (right - left) // 2

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


if __name__ == "__main__":
  lowercase__				:Any				   =       input('Enter numbers separated by comma:\n').strip()
  lowercase__				:Tuple				   =       sorted(int(item) for item in user_input.split(','))
  lowercase__				:int				   =       int(input('Enter a single number to be found in the list:\n'))
  lowercase__				:str				   =       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}.""")






"""simple docstring"""





import inspect
import unittest

import torch
import torch.nn as nn

from accelerate.hooks import (
    AlignDevicesHook,
    ModelHook,
    SequentialHook,
    add_hook_to_module,
    attach_align_device_hook,
    remove_hook_from_module,
    remove_hook_from_submodules,
)
from accelerate.test_utils import require_multi_gpu




class 							snake_case							(			nn.Module ):

      '''simple docstring'''



      def __init__(							self       :      List[Any] ):


        '''simple docstring'''




        super().__init__()
        __UpperCAmelCase    :						Dict       =						nn.Linear(3						,				4 )
        __UpperCAmelCase    :						Union[str, Any]       =						nn.BatchNormad(4 )
        __UpperCAmelCase    :						List[str]       =						nn.Linear(4						,				5 )







      def       A_					(							self       :      Any						,				__lowercase       :      Any ):


        '''simple docstring'''




        return self.lineara(self.batchnorm(self.lineara(__lowercase ) ) )




class 							snake_case							(			__UpperCAmelCase ):

      '''simple docstring'''



      def       A_					(							self       :      Union[str, Any]						,				__lowercase       :      Optional[int]						,				*__lowercase       :      str						,				**__lowercase       :      Optional[int] ):


        '''simple docstring'''




        return (args[0] + 1,) + args[1:], kwargs




class 							snake_case							(			__UpperCAmelCase ):

      '''simple docstring'''



      def       A_					(							self       :      Any						,				__lowercase       :      Tuple						,				__lowercase       :      Any ):


        '''simple docstring'''




        return output + 1




class 							snake_case							(			unittest.TestCase ):

      '''simple docstring'''



      def       A_					(							self       :      Optional[int] ):


        '''simple docstring'''




        __UpperCAmelCase    :						Dict       =						ModelForTest()
        __UpperCAmelCase    :						Optional[int]       =						ModelHook()

        add_hook_to_module(__lowercase						,				__lowercase )
        self.assertEqual(test_model._hf_hook						,				__lowercase )
        self.assertTrue(hasattr(__lowercase						,				'''_old_forward''' ) )

        # Check adding the hook did not change the name or the signature
        self.assertEqual(test_model.forward.__name__						,				'''forward''' )
        self.assertListEqual(list(inspect.signature(test_model.forward ).parameters )						,				['''x'''] )

        remove_hook_from_module(__lowercase )
        self.assertFalse(hasattr(__lowercase						,				'''_hf_hook''' ) )
        self.assertFalse(hasattr(__lowercase						,				'''_old_forward''' ) )

      def       A_					(							self       :      List[Any] ):


        '''simple docstring'''




        __UpperCAmelCase    :						str       =						ModelForTest()
        __UpperCAmelCase    :						Tuple       =						ModelHook()

        add_hook_to_module(__lowercase						,				__lowercase )
        add_hook_to_module(__lowercase						,				__lowercase						,				append=__lowercase )

        self.assertEqual(isinstance(test_model._hf_hook						,				__lowercase )						,				__lowercase )
        self.assertEqual(len(test_model._hf_hook.hooks )						,				2 )
        self.assertTrue(hasattr(__lowercase						,				'''_old_forward''' ) )

        # Check adding the hook did not change the name or the signature
        self.assertEqual(test_model.forward.__name__						,				'''forward''' )
        self.assertListEqual(list(inspect.signature(test_model.forward ).parameters )						,				['''x'''] )

        remove_hook_from_module(__lowercase )
        self.assertFalse(hasattr(__lowercase						,				'''_hf_hook''' ) )
        self.assertFalse(hasattr(__lowercase						,				'''_old_forward''' ) )

      def       A_					(							self       :      Any ):


        '''simple docstring'''




        __UpperCAmelCase    :						Dict       =						ModelForTest()
        __UpperCAmelCase    :						Tuple       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Optional[int]       =						test_model(x + 1 )
        __UpperCAmelCase    :						Optional[Any]       =						test_model(x + 2 )

        __UpperCAmelCase    :						Optional[int]       =						PreForwardHook()
        add_hook_to_module(__lowercase						,				__lowercase )
        __UpperCAmelCase    :						Union[str, Any]       =						test_model(__lowercase )
        self.assertTrue(torch.allclose(__lowercase						,				__lowercase						,				atol=1e-5 ) )

        # Attaching a hook to a model when it already has one replaces, does not chain
        __UpperCAmelCase    :						int       =						PreForwardHook()
        add_hook_to_module(__lowercase						,				__lowercase )
        __UpperCAmelCase    :						Any       =						test_model(__lowercase )
        self.assertTrue(torch.allclose(__lowercase						,				__lowercase						,				atol=1e-5 ) )

        # You need to use the sequential hook to chain two or more hooks
        __UpperCAmelCase    :						Any       =						SequentialHook(PreForwardHook()						,				PreForwardHook() )
        add_hook_to_module(__lowercase						,				__lowercase )

        __UpperCAmelCase    :						Tuple       =						test_model(__lowercase )
        assert torch.allclose(__lowercase						,				__lowercase						,				atol=1e-5 )

      def       A_					(							self       :      Any ):


        '''simple docstring'''




        __UpperCAmelCase    :						int       =						ModelForTest()
        __UpperCAmelCase    :						List[Any]       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Tuple       =						test_model(__lowercase )

        __UpperCAmelCase    :						int       =						PostForwardHook()
        add_hook_to_module(__lowercase						,				__lowercase )
        __UpperCAmelCase    :						Optional[int]       =						test_model(__lowercase )
        self.assertTrue(torch.allclose(__lowercase						,				output + 1						,				atol=1e-5 ) )

        # Attaching a hook to a model when it already has one replaces, does not chain
        __UpperCAmelCase    :						str       =						PostForwardHook()
        add_hook_to_module(__lowercase						,				__lowercase )
        __UpperCAmelCase    :						List[str]       =						test_model(__lowercase )
        self.assertTrue(torch.allclose(__lowercase						,				output + 1						,				atol=1e-5 ) )

        # You need to use the sequential hook to chain two or more hooks
        __UpperCAmelCase    :						Optional[int]       =						SequentialHook(PostForwardHook()						,				PostForwardHook() )
        add_hook_to_module(__lowercase						,				__lowercase )

        __UpperCAmelCase    :						Dict       =						test_model(__lowercase )
        assert torch.allclose(__lowercase						,				output + 2						,				atol=1e-5 )

      def       A_					(							self       :      Dict ):


        '''simple docstring'''




        __UpperCAmelCase    :						List[str]       =						ModelForTest()
        __UpperCAmelCase    :						Union[str, Any]       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						str       =						test_model(__lowercase )

        __UpperCAmelCase    :						Union[str, Any]       =						PostForwardHook()
        add_hook_to_module(__lowercase						,				__lowercase )
        __UpperCAmelCase    :						Optional[int]       =						test_model(__lowercase )
        self.assertTrue(torch.allclose(__lowercase						,				output + 1 ) )
        self.assertTrue(outputa.requires_grad )

        __UpperCAmelCase    :						Optional[Any]       =						True
        __UpperCAmelCase    :						int       =						test_model(__lowercase )
        self.assertFalse(outputa.requires_grad )

      @require_multi_gpu
      def       A_					(							self       :      List[str] ):


        '''simple docstring'''




        __UpperCAmelCase    :						Optional[Any]       =						ModelForTest()
        # Everything is on CPU
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # This will move each submodule on different devices
        add_hook_to_module(model.lineara						,				AlignDevicesHook(execution_device=0 ) )
        add_hook_to_module(model.batchnorm						,				AlignDevicesHook(execution_device=0 ) )
        add_hook_to_module(model.lineara						,				AlignDevicesHook(execution_device=1 ) )

        self.assertEqual(model.lineara.weight.device						,				torch.device(0 ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device(0 ) )
        self.assertEqual(model.batchnorm.running_mean.device						,				torch.device(0 ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device(1 ) )

        # We can still make a forward pass. The input does not need to be on any particular device
        __UpperCAmelCase    :						Dict       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Any       =						model(__lowercase )
        self.assertEqual(output.device						,				torch.device(1 ) )

        # We can add a general hook to put back output on same device as input.
        add_hook_to_module(__lowercase						,				AlignDevicesHook(io_same_device=__lowercase ) )
        __UpperCAmelCase    :						List[Any]       =						torch.randn(2						,				3 ).to(0 )
        __UpperCAmelCase    :						int       =						model(__lowercase )
        self.assertEqual(output.device						,				torch.device(0 ) )

      def       A_					(							self       :      Tuple ):


        '''simple docstring'''




        __UpperCAmelCase    :						Optional[Any]       =						ModelForTest()

        # Everything is on CPU
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # This will move each submodule on different devices
        __UpperCAmelCase    :						Tuple       =						{'''execution_device''': 0 if torch.cuda.is_available() else '''cpu''', '''offload''': True}

        add_hook_to_module(model.lineara						,				AlignDevicesHook(**__lowercase ) )
        add_hook_to_module(model.batchnorm						,				AlignDevicesHook(**__lowercase ) )
        add_hook_to_module(model.lineara						,				AlignDevicesHook(**__lowercase ) )

        # Parameters have been offloaded, so on the meta device
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        # Buffers are not included in the offload by default, so are on the execution device
        __UpperCAmelCase    :						Optional[int]       =						torch.device(hook_kwargs['''execution_device'''] )
        self.assertEqual(model.batchnorm.running_mean.device						,				__lowercase )

        __UpperCAmelCase    :						int       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Optional[int]       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_module(model.lineara )
        remove_hook_from_module(model.batchnorm )
        remove_hook_from_module(model.lineara )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # Now test with buffers included in the offload
        __UpperCAmelCase    :						str       =						{
            '''execution_device''': 0 if torch.cuda.is_available() else '''cpu''',
            '''offload''': True,
            '''offload_buffers''': True,
        }

        add_hook_to_module(model.lineara						,				AlignDevicesHook(**__lowercase ) )
        add_hook_to_module(model.batchnorm						,				AlignDevicesHook(**__lowercase ) )
        add_hook_to_module(model.lineara						,				AlignDevicesHook(**__lowercase ) )

        # Parameters have been offloaded, so on the meta device, buffers included
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.running_mean.device						,				torch.device('''meta''' ) )

        __UpperCAmelCase    :						Optional[Any]       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						List[Any]       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_module(model.lineara )
        remove_hook_from_module(model.batchnorm )
        remove_hook_from_module(model.lineara )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

      def       A_					(							self       :      List[str] ):


        '''simple docstring'''




        __UpperCAmelCase    :						List[str]       =						ModelForTest()

        # Everything is on CPU
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # This will move each submodule on different devices
        __UpperCAmelCase    :						Optional[Any]       =						0 if torch.cuda.is_available() else '''cpu'''
        attach_align_device_hook(__lowercase						,				execution_device=__lowercase						,				offload=__lowercase )

        # Parameters have been offloaded, so on the meta device
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        # Buffers are not included in the offload by default, so are on the execution device
        __UpperCAmelCase    :						Dict       =						torch.device(__lowercase )
        self.assertEqual(model.batchnorm.running_mean.device						,				__lowercase )

        __UpperCAmelCase    :						Optional[int]       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Dict       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_submodules(__lowercase )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # Now test with buffers included in the offload
        attach_align_device_hook(__lowercase						,				execution_device=__lowercase						,				offload=__lowercase						,				offload_buffers=__lowercase )

        # Parameters have been offloaded, so on the meta device, buffers included
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.running_mean.device						,				torch.device('''meta''' ) )

        __UpperCAmelCase    :						Dict       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						str       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_submodules(__lowercase )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )







      def       A_					(							self       :      Any ):


        '''simple docstring'''




        __UpperCAmelCase    :						Dict       =						ModelForTest()

        # Everything is on CPU
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # This will move each submodule on different devices
        __UpperCAmelCase    :						str       =						0 if torch.cuda.is_available() else '''cpu'''
        attach_align_device_hook(
            __lowercase						,				execution_device=__lowercase						,				offload=__lowercase						,				weights_map=model.state_dict() )

        # Parameters have been offloaded, so on the meta device
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        # Buffers are not included in the offload by default, so are on the execution device
        __UpperCAmelCase    :						Optional[Any]       =						torch.device(__lowercase )
        self.assertEqual(model.batchnorm.running_mean.device						,				__lowercase )

        __UpperCAmelCase    :						Any       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Dict       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_submodules(__lowercase )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )

        # Now test with buffers included in the offload
        attach_align_device_hook(
            __lowercase						,				execution_device=__lowercase						,				offload=__lowercase						,				weights_map=model.state_dict()						,				offload_buffers=__lowercase						,				)

        # Parameters have been offloaded, so on the meta device, buffers included
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''meta''' ) )
        self.assertEqual(model.batchnorm.running_mean.device						,				torch.device('''meta''' ) )

        __UpperCAmelCase    :						List[str]       =						torch.randn(2						,				3 )
        __UpperCAmelCase    :						Optional[int]       =						model(__lowercase )
        self.assertEqual(output.device						,				__lowercase )

        # Removing hooks loads back the weights in the model.
        remove_hook_from_submodules(__lowercase )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.batchnorm.weight.device						,				torch.device('''cpu''' ) )
        self.assertEqual(model.lineara.weight.device						,				torch.device('''cpu''' ) )