1. 引言：高效查找的需求

在許多應(yīng)用場景中，我們經(jīng)常需要在一個數(shù)據(jù)集合中快速定位某個特定元素或其附近元素。例如，假設(shè)我們有一個包含row對象的列表，每個row對象有兩個整型字段a和b。數(shù)據(jù)組織方式是，如果按a字段排序，則b字段也自動有序。我們的目標是編寫一個函數(shù)，給定一個整數(shù)x，能夠找到列表中b字段值恰好在x之后（或等于x）的第一個row對象。

當列表中的記錄數(shù)量較少時，通過迭代整個列表進行線性查找可能是一個簡單直接的方法。然而，當記錄數(shù)量達到數(shù)百甚至數(shù)千（例如1000條記錄）時，線性迭代的效率會顯著降低，導(dǎo)致應(yīng)用程序響應(yīng)變慢。在這種情況下，我們需要一種更高效的數(shù)據(jù)查找策略，避免不必要的全量遍歷。

2. 二分查找基礎(chǔ)與Collections.binarySearch()

為了解決上述性能問題，二分查找（Binary Search）是理想的選擇。二分查找是一種在有序數(shù)組中查找特定元素的算法，其核心思想是每次將搜索區(qū)間減半，從而大大減少查找次數(shù)。它的時間復(fù)雜度為O(log N)，遠優(yōu)于線性查找的O(N)。

在Java中，java.util.Collections類提供了binarySearch()方法，可以方便地對List進行二分查找。對于包含自定義對象的列表，我們需要使用以下重載方法：

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

• list: 要搜索的已排序列表。
• key: 要搜索的元素。對于自定義對象，通常需要構(gòu)造一個“虛擬”的鍵對象，其相關(guān)字段與我們要查找的值匹配。
• c: 一個Comparator對象，用于定義列表中元素的排序規(guī)則以及key與列表中元素的比較規(guī)則。

binarySearch()方法的返回值是其關(guān)鍵：

立即學習“Java免費學習筆記（深入）”；

• 如果找到精確匹配的元素，則返回該元素的索引（非負數(shù)）。
• 如果未找到精確匹配的元素，則返回一個負數(shù)。這個負數(shù)的計算方式是 (-(insertion point) - 1)，其中insertion point是如果key被插入到列表中以保持其排序順序，它將位于的索引。例如，如果key小于列表中所有元素，則insertion point為0；如果key大于列表中所有元素，則insertion point為list.size()。

3. 實現(xiàn)步驟與代碼示例

接下來，我們將詳細展示如何利用Collections.binarySearch()來實現(xiàn)高效查找。

3.1 定義Row類

首先，定義我們的自定義對象Row，它包含a和b兩個整型字段。

static class Row {
    int a, b; // 假設(shè)a和b字段
    public int getA() { return a; } // getter方法
    public int getB() { return b; } // getter方法

    // 構(gòu)造函數(shù)
    Row(int a, int b) {
        this.a = a;
        this.b = b;
    }

    // 方便打印的toString方法
    @Override
    public String toString() {
        return "Row(" + a + ", " + b + ")";
    }
}

3.2 定義Comparator

由于我們需要根據(jù)b字段進行查找，因此需要一個Comparator來定義Row對象之間基于b字段的比較邏輯。

// 定義一個靜態(tài) final 的 Comparator，用于按b字段排序
static final Comparator<Row> ORDER_BY_B = Comparator.comparing(Row::getB);

這里使用了Java 8的Comparator.comparing()方法，它通過方法引用Row::getB簡潔地創(chuàng)建了一個比較器。

3.3 實現(xiàn)查找函數(shù)find

現(xiàn)在，我們可以實現(xiàn)核心的find函數(shù)。這個函數(shù)將接收一個目標值x和Row對象的列表，并返回符合條件的Row對象。

static Row find(int x, List<Row> rows) {
    int size = rows.size();
    if (size == 0) { // 處理空列表情況
        return null; // 或者拋出 IllegalArgumentException
    }

    // 構(gòu)造一個臨時的Row對象作為查找鍵。
    // 它的a值不重要，因為我們的Comparator只關(guān)注b值。
    int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B);

    // 根據(jù)binarySearch的返回值確定最終的索引
    int index;
    if (i >= 0) {
        // 情況1: 找到了精確匹配的元素 (即某個Row的b值正好等于x)
        index = i;
    } else {
        // 情況2: 未找到精確匹配的元素
        // -i - 1 是元素如果被插入以保持排序順序，它應(yīng)該在的索引 (insertion point)
        int insertionPoint = -i - 1;

        if (insertionPoint >= size) {
            // 子情況2.1: x 大于列表中所有元素的b值。
            // 此時，insertionPoint 會等于 size。
            // 根據(jù)需求“b comes right after x”，如果x比所有b都大，
            // 則返回列表中b值最大的那個元素（即最后一個元素）。
            index = size - 1;
        } else {
            // 子情況2.2: x 介于列表中某些元素之間，或者 x 小于所有元素。
            // insertionPoint 就是第一個b值大于或等于x的元素的索引。
            index = insertionPoint;
        }
    }
    // 返回找到的Row對象
    return rows.get(index);
}

3.4 主函數(shù)示例

為了演示上述代碼的用法，我們創(chuàng)建一個main方法，初始化一個Row列表，并對其進行查找。

public static void main(String[] args) {
    // 原始數(shù)據(jù)列表
    List<Row> rows = Arrays.asList(
        new Row(20, 2),
        new Row(40, 4),
        new Row(50, 5),
        new Row(70, 7)
    );

    // 確保列表是按照b值排序的。
    // 如果原始列表rows本身不是按b字段排序的，
    // 則在進行二分查找前必須先進行一次排序。
    List<Row> orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());

    System.out.println("查找結(jié)果:");
    // 遍歷不同的x值進行查找，觀察結(jié)果
    for (int i = 0; i < 9; ++i) {
        System.out.println("find " + i + " : " + find(i, orderByB));
    }
}

運行上述main方法，將得到如下輸出：

查找結(jié)果:
find 0 : Row(20, 2)
find 1 : Row(20, 2)
find 2 : Row(20, 2)
find 3 : Row(40, 4)
find 4 : Row(40, 4)
find 5 : Row(50, 5)
find 6 : Row(70, 7)
find 7 : Row(70, 7)
find 8 : Row(70, 7)

從輸出可以看出，當x為0、1、2時，返回的是b值為2的Row(20, 2)，這是列表中第一個b值大于或等于x的元素。當x為8時，由于沒有b值大于8的元素，它返回了列表中b值最大的元素Row(70, 7)。這與我們對“最近元素”或“緊隨其后”的理解相符。

4. 注意事項與性能考量

• 數(shù)據(jù)預(yù)排序： Collections.binarySearch()方法要求其操作的列表必須是已排序的。如果傳入的列表沒有按照Comparator定義的規(guī)則進行排序，那么binarySearch()的結(jié)果將是不可預(yù)測的。在我們的示例中，如果原始rows列表不是按b值排序的，我們必須先調(diào)用rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList())進行一次排序。這次排序操作的時間復(fù)雜度為O(N log N)。
• 查找性能： 一旦列表完成排序，每次find操作的時間復(fù)雜度僅為O(log N)。對于包含1000個元素的列表，線性查找可能需要最多1000次比較，而二分查找最多只需要約log?1000 ≈ 10次比較，性能提升顯著。
• 查找鍵的構(gòu)造： 在find函數(shù)中，我們使用new Row(0, x)作為key傳入binarySearch。這里的Row對象的a字段值（0）是任意的，因為它不會被ORDER_BY_B這個Comparator所使用。Comparator只關(guān)注key對象的b字段值與列表中元素的b字段值進行比較。
• 返回值處理的精確性： 對binarySearch返回值的正確理解和處理是實現(xiàn)此功能的關(guān)鍵。特別是當沒有精確匹配時，通過insertion point的概念，我們可以準確地找到“第一個大于或等于”目標值的元素，以及處理目標值大于所有元素的情況。
• 邊界情況： 我們的find函數(shù)考慮了空列表的情況（返回null）。此外，它也正確處理了x小于所有b值（返回第一個元素）和x大于所有b值（返回最后一個元素）的邊界情況。

5. 總結(jié)

在Java中，當需要從一個大型、已排序的自定義對象列表中高效查找特定元素或其附近元素時，Collections.binarySearch()方法是一個極其強大且高效的工具。通過結(jié)合自定義的Comparator，我們可以靈活地定義查找的依據(jù)，并利用二分查找的對數(shù)時間復(fù)雜度優(yōu)勢，顯著提升應(yīng)用程序的性能。理解binarySearch()的返回值及其在不同場景下的含義，是正確實現(xiàn)此類查找功能的關(guān)鍵。在合適的場景下，積極采用二分查找能夠有效優(yōu)化數(shù)據(jù)密集型操作的性能。

以上就是Java中高效查找排序?qū)ο罅斜碇凶罱氐姆椒ǖ脑敿殐?nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！