


'''simple docstring'''

from __future__ import annotations

import bisect






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int = 0      ,  __lowerCamelCase		: int = -1				)      ->     int:







     '''simple docstring'''






     if hi < 0:
          _a						=		len(__lowerCamelCase				)

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

     return lo






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int = 0      ,  __lowerCamelCase		: int = -1				)      ->     int:







     '''simple docstring'''






     if hi < 0:
          _a						=		len(__lowerCamelCase				)

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

     return lo






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int = 0      ,  __lowerCamelCase		: int = -1				)      ->     None:







     '''simple docstring'''






     sorted_collection.insert(bisect_left(__lowerCamelCase      ,  __lowerCamelCase      ,  __lowerCamelCase      ,  __lowerCamelCase				)      ,  __lowerCamelCase				)






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int = 0      ,  __lowerCamelCase		: int = -1				)      ->     None:







     '''simple docstring'''






     sorted_collection.insert(bisect_right(__lowerCamelCase      ,  __lowerCamelCase      ,  __lowerCamelCase      ,  __lowerCamelCase				)      ,  __lowerCamelCase				)






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int				)      ->     int | None:







     '''simple docstring'''






     _a						=		0
     _a						=		len(__lowerCamelCase				) - 1

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






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int				)      ->     int | None:







     '''simple docstring'''






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






def __UpperCamelCase   (			__lowerCamelCase		: list[int]      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int      ,  __lowerCamelCase		: int				)      ->     int | None:







     '''simple docstring'''






     if right < left:
          return None

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

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


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

lowercase__				     =		256
# Modulus to hash a string
lowercase__				     =		1_000_003






def __UpperCamelCase   (			__lowerCamelCase		: str      ,  __lowerCamelCase		: str				)      ->     bool:







     '''simple docstring'''






     _a						=		len(__lowerCamelCase				)
     _a						=		len(__lowerCamelCase				)
     if p_len > t_len:
          return False

     _a						=		0
     _a						=		0
     _a						=		1

     # Calculating the hash of pattern and substring of text
     for i in range(__lowerCamelCase				):
          _a						=		(ord(pattern[i]				) + p_hash * alphabet_size) % modulus
          _a						=		(ord(text[i]				) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          _a						=		(modulus_power * alphabet_size) % modulus

     for i in range(0      ,  t_len - p_len + 1				):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          _a						=		(
              (text_hash - ord(text[i]				) * modulus_power) * alphabet_size
              + ord(text[i + p_len]				)
          ) % modulus
     return False






def __UpperCamelCase   (			)      ->     None:







     '''simple docstring'''






     _a						=		"abc1abc12"
     _a						=		"alskfjaldsabc1abc1abc12k23adsfabcabc"
     _a						=		"alskfjaldsk23adsfabcabc"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				) and not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 2)
     _a						=		"ABABX"
     _a						=		"ABABZABABYABABX"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 3)
     _a						=		"AAAB"
     _a						=		"ABAAAAAB"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 4)
     _a						=		"abcdabcy"
     _a						=		"abcxabcdabxabcdabcdabcy"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 5)
     _a						=		"Lü"
     _a						=		"Lüsai"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     _a						=		"Lue"
     assert not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     print("Success."				)


if __name__ == "__main__":
   test_rabin_karp()

