

'''simple docstring'''

def 							_UpperCamelCase				(   lowerCAmelCase__:					list   )      -> list:
							SCREAMING_SNAKE_CASE_				=				len(__lowerCamelCase   )
							for i in range(1		,__lowerCamelCase   ):
														SCREAMING_SNAKE_CASE_				=				collection[i]
														SCREAMING_SNAKE_CASE_				=				0
														SCREAMING_SNAKE_CASE_				=				i - 1

														while low <= high:
																					SCREAMING_SNAKE_CASE_				=				(low + high) // 2
																					if val < collection[mid]:
																												SCREAMING_SNAKE_CASE_				=				mid - 1
																					else:
																												SCREAMING_SNAKE_CASE_				=				mid + 1
														for j in range(__lowerCamelCase		,__lowerCamelCase		,-1   ):
																					SCREAMING_SNAKE_CASE_				=				collection[j - 1]
														SCREAMING_SNAKE_CASE_				=				val
							return collection


if __name__ == "__main__":
							SCREAMING_SNAKE_CASE							:				int     	=			input("Enter numbers separated by a comma:\n").strip()
							SCREAMING_SNAKE_CASE							:				List[Any]     	=			[int(item) for item in user_input.split(",")]
							print(binary_insertion_sort(unsorted))










from __future__ import annotations






class     __a			:



	def __init__(    self				:     List[Any]					,						snake_case_				:     str					,						snake_case_				:     str)->				Optional[int]:
						__lowerCAmelCase ,						__lowerCAmelCase						 =text, pattern
						__lowerCAmelCase ,						__lowerCAmelCase						 =len(snake_case_), len(snake_case_)



	def 		UpperCamelCase				(    self				:     List[Any]					,						snake_case_				:     str)->				int:

						for i in range(self.patLen - 1					,						-1					,						-1):
											if char == self.pattern[i]:
																return i
						return -1



	def 		UpperCamelCase				(    self				:     List[str]					,						snake_case_				:     int)->				int:

						for i in range(self.patLen - 1					,						-1					,						-1):
											if self.pattern[i] != self.text[current_pos + i]:
																return current_pos + i
						return -1



	def 		UpperCamelCase				(    self				:     Dict)->				list[int]:
						# searches pattern in text and returns index positions
						__lowerCAmelCase						 =[]
						for i in range(self.textLen - self.patLen + 1):
											__lowerCAmelCase						 =self.mismatch_in_text(snake_case_)
											if mismatch_index == -1:
																positions.append(snake_case_)
											else:
																__lowerCAmelCase						 =self.match_in_pattern(self.text[mismatch_index])
																__lowerCAmelCase						 =(
																    mismatch_index - match_index
																)  # shifting index lgtm [py/multiple-definition]
						return positions


lowercase_													=      '''ABAABA'''
lowercase_													=      '''AB'''
lowercase_													=      BoyerMooreSearch(text, pattern)
lowercase_													=      bms.bad_character_heuristic()

if len(positions) == 0:
				print('''No match found''')
else:
				print('''Pattern found in following positions: ''')
				print(positions)




