Java 資料結構查找演算法詳解：線性、二分、分塊索引與雜湊表

1. 線性表查找

• 順序查找：從頭遍歷陣列/列表，時間複雜度 O(n)。
• 鏈式查找：遍歷鏈表節點，同樣 O(n)。

2. 二分查找 (Binary Search)

前提：資料結構為順序儲存且已排序。每次與中間值比較，範圍減半，時間複雜度 O(log n)。

public static int binarySearch(int[] arrays, int key) {
    int start = 0, end = arrays.length - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arrays[mid] == key) return mid;
        if (arrays[mid] < key) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}

3. 分塊索引查找 (Indexed Sequential Search)

概念：建立索引表 (如字典首字母索引)，先查索引定位區塊，再在區塊內查找 (可用二分)。

// 索引項目
class IndexItem implements Comparable<IndexItem> {
    String firstChar; int startIndex;
    // 建構子、compareTo 略
}
// 查找流程：二分查索引 -> 確定區塊範圍 -> 二分查關鍵字陣列

4. 雜湊表查找 (Hash Table Search)

核心：雜湊函數 + 衝突解決 (鏈接法)。平均查找 O(1)。

public class HashSet<T> {
    private SingleLinkedList<T>[] table;
    public HashSet(int size) {
        table = new SingleLinkedList[Math.abs(size)];
        for (int i = 0; i < table.length; i++) table[i] = new SingleLinkedList<>();
    }
    private int hash(T x) { return Math.abs(x.hashCode()) % table.length; }
    public void insert(T x) { table[hash(x)].insert(0, x); }
    public T search(T key) { return table[hash(key)].search(key); }
}

總結比較