输入数组A[1..n]，改进插入排序算法InsertSort(A)，在插入元素A[i]时用二分查找代替顺序查找写出Python代码

改进后的插入排序（也称为二分插入排序），当插入元素时，会利用已排序部分的有序特性，通过二分查找快速定位到合适的位置，而不是逐个比较。以下是这个优化版本的Python实现：

def binary_insertion_sort(arr):
    if len(arr) <= 1:
        return arr
    
    for i in range(1, len(arr)):
        key = arr[i]
        
        # 使用二分查找找到键值应该插入的位置
        low = 0
        high = i - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] > key:
                high = mid - 1
            else:
                low = mid + 1
                
        # 插入键值到正确位置
        arr = arr[:mid+1] + [key] + arr[mid+1:]
    
    return arr

# 示例
A = [5, 3, 8, 6, 4, 7, 9]
binary_insertion_sort(A)
print(A)

在这个优化版的插入排序中，每次迭代都会减少一半的无序区间，因此整体时间复杂度仍然保持在O(n^2)，但在实践中可能会更快，尤其是对于近乎有序的输入。