2. def insertionSort(arr):
    3.     for i in range(1, len(arr)):
    4.         key = arr[i]
    5.         j = i - 1
    6.         while j >= 0 and key < arr[j]:
    7.             arr[j + 1] = arr[j]
    8.             j -= 1
    9.         arr[j + 1] = key
    11. arr = [1,9,6,5,3,46]
    12. insertionSort(arr)
    13. for i in range(len(arr)):
    14.     print("%d" % arr[i])
    17. def harfSearch(array, key, low, high):
    18.     mid = int((low+high)/2)
    19.     if key == array[mid]:
    20.         return array[mid]
    21.     if low > high:
    22.         return False
    23.     if key < array[mid]:
    24.         return harfSearch(array, key, low, mid-1)
    25.     if key > array[mid]:
    26.         return harfSearch(array, key, mid+1, high)
    28. if __name__ == "__main__":
    29.     array = [4, 13, 9, 6, 5, 55, 65, 76, 97]
    30.     ret = harfSearch(array, 76, 0, len(array)-1)
    31.     print(ret)
    33.     def k_small(self, matrix: List[List[int]], k: int) -> int:
    34.         def search(mid, n):
    35.             i, j = n - 1, 0
    36.             count = 0
    37.             while i >= 0 and j < n:
    38.                 if matrix[i][j] <= mid:
    39.                     count += (i + 1)
    40.                     j += 1
    41.                 else:
    42.                     i -= 1
    43.             return count >= k
    45.         n = len(matrix)
    47.         left, right = matrix[0][0], matrix[n - 1][n - 1]
    49.         while left < right:
    50.             mid = left + (right - left) // 2
    51.             if search(mid, n):
    52.                 right = mid
    53.             else:
    54.                 left = mid + 1
    55.         return left