





"""simple docstring"""




def  a_       (							_lowercase ,		_lowercase ,		_lowercase ,		_lowercase     ):
						_UpperCamelCase    :      str						     =					int((lower_bound + upper_bound) // 2     )
						if array[r] == value:
												return r
						if lower_bound >= upper_bound:
												return -1
						if array[r] < value:
												return binary_search(_lowercase ,		r + 1 ,		_lowercase ,		_lowercase     )
						else:
												return binary_search(_lowercase ,		_lowercase ,		r - 1 ,		_lowercase     )





def  a_       (							_lowercase ,		_lowercase     ):
						_UpperCamelCase    :      List[Any]						     =					0
						if matrix[index][0] == value:
												return [index, 0]
						while index < len(_lowercase     ) and matrix[index][0] < value:
												_UpperCamelCase    :      Any						     =					binary_search(matrix[index] ,		0 ,		len(matrix[index]     ) - 1 ,		_lowercase     )
												if r != -1:
																		return [index, r]
												index += 1
						return [-1, -1]


if __name__ == "__main__":
						import doctest

						doctest.testmod()










"""simple docstring"""




def  a_       (							_lowercase     ):
						if len(_lowercase     ) > 1:
												_UpperCamelCase    :      List[str]						     =					len(_lowercase     ) // 2  # Finds the middle of the array
												_UpperCamelCase    :      Dict						     =					arr[
												    :middle_length
												]  # Creates an array of the elements in the first half.
												_UpperCamelCase    :      Union[str, Any]						     =					arr[
												    middle_length:
												]  # Creates an array of the elements in the second half.
												_UpperCamelCase    :      str						     =					len(_lowercase     )
												_UpperCamelCase    :      List[str]						     =					len(_lowercase     )
												merge(_lowercase     )  # Starts sorting the left.
												merge(_lowercase     )  # Starts sorting the right
												_UpperCamelCase    :      Dict						     =					0  # Left Counter
												_UpperCamelCase    :      Union[str, Any]						     =					0  # Right Counter
												_UpperCamelCase    :      Optional[int]						     =					0  # Position Counter
												while (
												    left_index < left_size and right_index < right_size
												):  # Runs until the lowers size of the left and right are sorted.
																		if left_array[left_index] < right_array[right_index]:
																								_UpperCamelCase    :      Dict						     =					left_array[left_index]
																								left_index += 1
																		else:
																								_UpperCamelCase    :      Tuple						     =					right_array[right_index]
																								right_index += 1
																		index += 1
												while (
												    left_index < left_size
												):  # Adds the left over elements in the left half of the array
																		_UpperCamelCase    :      int						     =					left_array[left_index]
																		left_index += 1
																		index += 1
												while (
												    right_index < right_size
												):  # Adds the left over elements in the right half of the array
																		_UpperCamelCase    :      Any						     =					right_array[right_index]
																		right_index += 1
																		index += 1
						return arr


if __name__ == "__main__":
						import doctest

						doctest.testmod()



