#include <stdio.h>

// 二分查找函数，用于在已排序部分找到插入位置
int binarySearch(int arr[], int target, int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;  // 返回插入的位置
}

// 折半插入排序函数
void binaryInsertionSort(int arr[], int length) {
    for (int i = 1; i < length; i++) {
        int currentElement = arr[i];
        // 使用二分查找来找到当前元素的插入位置
        int insertPosition = binarySearch(arr, currentElement, 0, i - 1);
        
        // 将已排序部分的元素后移，为当前元素腾出位置
        for (int j = i; j > insertPosition; j--) {
            arr[j] = arr[j - 1];
        }
        
        // 将当前元素插入到合适的位置
        arr[insertPosition] = currentElement;
    }
}

// 测试折半插入排序
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int length = sizeof(arr) / sizeof(arr[0]);  // 获取数组长度
    
    printf("排序前：");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    
    binaryInsertionSort(arr, length);  // 调用折半插入排序
    
    printf("\n排序后：");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}
