3from random import randint
 4
 5
 6def sort_array(arr: list) -> list:  # Works for arrays: 1 <= nums.length <= 5 * 104; -5 * 104 <= nums[i] <= 5 * 104 7    if len(arr) <= 1:
 8        return arr
 9    middle = len(arr) // 2

16
17
18# recursive binary search
19def binary_recur(arr: list, start: int, end: int, target: int) -> int:  # use only with sorted array20    if end >= start:
21        mid = start + end - 1 // 2
22