Java 二分查找與二分插入排序算法實現詳解

二分查找

前提：數組必須有序。時間複雜度 O(log₂N)，數據量越大優勢越明顯。例如 200 個元素，最多查找 8 次 (2⁷=128, 2⁸=256)。

迭代實現

static int binarySearch(int[] array, int data) {
    int start = 0, end = array.length - 1, mid = -1;
    while (start <= end) {
        mid = (start + end) >>> 1;  // 無符號右移防溢出
        if (array[mid] < data) {
            start = mid + 1;
        } else if (array[mid] > data) {
            end = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

遞歸實現

static int binarySearch4Recursion(int[] array, int data, int start, int end) {
    if (start > end) return -1;
    int mid = (start + end) >>> 1;
    if (array[mid] < data) {
        return binarySearch4Recursion(array, data, mid + 1, end);
    } else if (array[mid] > data) {
        return binarySearch4Recursion(array, data, start, mid - 1);
    } else {
        return mid;
    }
}

二分插入排序

在直接插入排序基礎上，查找插入位置時改用二分查找，減少比較次數。
時間複雜度仍為 O(N²)（移動元素開銷不變），但對隨機無序序列比較次數顯著減少；對基本有序序列不如直接插入排序。

完整實現（降序示例）

public class BinaryInsertSort {
    public static void main(String[] args) {
        int len = 10;
        int[] ary = new int[len];
        Random random = new Random();
        for (int j = 0; j < len; j++) ary[j] = random.nextInt(1000);

        binaryInsert(ary);
        printArray(ary);
    }

    private static void binaryInsert(int[] ary) {
        int setValueCount = 0;
        for (int j = 1; j < ary.length; j++) {
            int key = ary[j];
            // 二分查找插入位置（降序）
            int index = binarySearchDesc2(ary, key, 0, j - 1);
            // 向右移動騰出位置
            for (int i = j; i > index; i--) {
                ary[i] = ary[i - 1];
                setValueCount++;
            }
            ary[index] = key;
            setValueCount++;
        }
        System.out.println("\n賦值次數: " + setValueCount);
    }

    // 非遞歸二分查找（降序）
    private static int binarySearchDesc2(int[] ary, int target, int from, int to) {
        for (; from < to; ) {
            int mid = (from + to) >>> 1;
            if (ary[mid] > target) {
                from = mid + 1;
            } else {
                to = mid - 1;
            }
        }
        return (ary[from] > target) ? from + 1 : from;
    }

    private static void printArray(int[] ary) {
        for (int i : ary) System.out.print(i + " ");
    }
}

運行輸出示例

-------排序前------
918 562 442 531 210 216 931 706 333 132
第1個索引上的元素要插入的位置是：1
...
第9個索引上的元素要插入的位置是：9
賦值次數 =====> 24
931 918 706 562 531 442 333 216 210 132

總結

• 二分查找是有序數組查找的首選，迭代版本無棧溢出風險，生產環境推薦。
• 二分插入排序優化了比較次數，但無法改變 O(N²) 的整體複雜度，適合數據量較小或近乎有序的場景。
• 實際項目中，大數據量排序優先考慮 Arrays.sort() (Dual-Pivot Quicksort) 或 Collections.sort() (TimSort)。