Java集合元素搜索算法

在Java中，有多種算法可以用于搜索集合中的元素。以下是一些常用的搜索算法：

1. 線性搜索（Linear Search）：這是最簡單的搜索算法，它按順序檢查集合中的每個元素，直到找到所需的元素或遍歷完整個集合。線性搜索的時間復雜度為O(n)，其中n是集合的大小。

public static int linearSearch(List<Integer> list, int target) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == target) {
            return i;
        }
    }
    return -1;
}

2. 二分搜索（Binary Search）：二分搜索是一種更高效的搜索算法，它要求集合是有序的。算法首先將目標值與集合中間的元素進行比較，如果目標值等于中間元素，則搜索成功。如果目標值小于中間元素，則在集合的左半部分繼續搜索；如果目標值大于中間元素，則在集合的右半部分繼續搜索。這個過程會不斷重復，直到找到目標值或搜索范圍為空。二分搜索的時間復雜度為O(log n)。

public static int binarySearch(List<Integer> list, int target) {
    int left = 0;
    int right = list.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (list.get(mid) == target) {
            return mid;
        } else if (list.get(mid) < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

3. 散列搜索（Hash Search）：散列搜索是一種基于散列表（Hash Table）的搜索算法。它通過計算元素的散列值來定位元素在散列表中的位置。散列搜索的平均時間復雜度為O(1)，但在最壞情況下（所有元素都映射到同一個散列值），時間復雜度可能會退化為O(n)。散列搜索需要額外的空間來存儲散列表。

import java.util.HashMap;
import java.util.Map;

public static int hashSearch(Map<Integer, Integer> map, int target) {
    return map.getOrDefault(target, -1);
}

4. 樹形結構搜索（Tree Search）：樹形結構搜索是一種基于樹形數據結構的搜索算法。它利用樹的層次關系來快速定位目標值。常見的樹形結構有二叉搜索樹（BST）、AVL樹等。樹形結構搜索的時間復雜度取決于樹的高度，最壞情況下（樹完全不平衡），時間復雜度可能會退化為O(n)。

import java.util.TreeMap;

public static int treeSearch(TreeMap<Integer, Integer> treeMap, int target) {
    Integer result = treeMap.get(target);
    return result != null ? result : -1;
}

這些搜索算法在不同的場景下有各自的優缺點。線性搜索適用于無序集合，二分搜索適用于有序集合，散列搜索適用于需要快速查找的場景，樹形結構搜索適用于需要維護有序數據結構的場景。在實際應用中，可以根據具體需求選擇合適的搜索算法。