java二分查找插入法

在Java中实现一个基于二分查找的插入排序法（虽然这里可能有些概念上的混淆，因为二分查找通常用于查找，而不是排序；但我们可以考虑在一个已排序的数组中，使用二分查找来确定插入新元素的位置，然后执行插入操作），以下是一个简单的实现示例：

public class BinarySearchInsertionSort {

    public static void binarySearchInsertion(int[] arr, int key) {
        if (arr == null || arr.length == 0) return;

        int n = arr.length;
        int[] temp = new int[n + 1];

        // 复制原数组到临时数组，并在末尾添加要插入的元素
        for (int i = 0; i < n; i++) {
            temp[i] = arr[i];
        }
        temp[n] = key;

        // 对临时数组进行排序（实际上是找到插入位置并移动元素）
        for (int i = n; i > 0; i--) {
            int elem = temp[i];
            int j;

            // 使用二分查找找到插入位置
            int low = 0, high = i - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (elem < temp[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            // 插入位置在 low
            for (j = i; j > low; j--) {
                temp[j] = temp[j - 1];
            }
            temp[j] = elem;
        }

        // 将排序后的临时数组复制回原数组
        for (int i = 0; i <= n; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 4;

        binarySearchInsertion(arr, key);

        // 打印排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

注意：这个示例实际上是在执行一个插入排序，但在查找插入位置时使用了二分查找法来优化查找过程。这可以显著提高在大型已排序数组中插入元素的效率。然而，如果数组本身未排序，则首先需要对数组进行排序，这通常不会使用二分查找插入法来实现。

此外，上述代码中的`binarySearchInsertion`函数接受一个数组和一个要插入的键，然后在数组中找到合适的插入位置，并将键插入到该位置。它使用了一个临时数组来避免在原始数组上进行直接修改，以保持函数的纯净性和避免不必要的副作用。最后，将排序（即插入）后的数组复制回原始数组。