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

在插入排序的基础上，我们可以结合二分查找优化插入操作，这称为二分插入排序。以下是使用Python实现的示例：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

def improved_insertion_sort(arr):
    for i in range(1, len(arr)):
        # 使用二分查找找到已排序部分的插入位置
        index = binary_search(arr[:i], arr[i])
        
        # 将元素插入到正确的位置
        arr = arr[:index] + [arr[i]] + arr[index:i] + arr[i+1:]
    return arr

# 示例输入数组
A = [5, 2, 8, 4, 9, 1]
sorted_A = improved_insertion_sort(A)
print("Sorted array:", sorted_A)