Java集合元素搜索算法

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

1. 線性搜索（Linear Search）：這是最簡(jiǎn)單的搜索算法，它按順序檢查集合中的每個(gè)元素，直到找到所需的元素或遍歷完整個(gè)集合。線性搜索的時(shí)間復(fù)雜度為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）：二分搜索是一種更高效的搜索算法，它要求集合是有序的。算法首先將目標(biāo)值與集合中間的元素進(jìn)行比較，如果目標(biāo)值等于中間元素，則搜索成功。如果目標(biāo)值小于中間元素，則在集合的左半部分繼續(xù)搜索；如果目標(biāo)值大于中間元素，則在集合的右半部分繼續(xù)搜索。這個(gè)過(guò)程會(huì)不斷重復(fù)，直到找到目標(biāo)值或搜索范圍為空。二分搜索的時(shí)間復(fù)雜度為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）的搜索算法。它通過(guò)計(jì)算元素的散列值來(lái)定位元素在散列表中的位置。散列搜索的平均時(shí)間復(fù)雜度為O(1)，但在最壞情況下（所有元素都映射到同一個(gè)散列值），時(shí)間復(fù)雜度可能會(huì)退化為O(n)。散列搜索需要額外的空間來(lái)存儲(chǔ)散列表。

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

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

4. 樹(shù)形結(jié)構(gòu)搜索（Tree Search）：樹(shù)形結(jié)構(gòu)搜索是一種基于樹(shù)形數(shù)據(jù)結(jié)構(gòu)的搜索算法。它利用樹(shù)的層次關(guān)系來(lái)快速定位目標(biāo)值。常見(jiàn)的樹(shù)形結(jié)構(gòu)有二叉搜索樹(shù)（BST）、AVL樹(shù)等。樹(shù)形結(jié)構(gòu)搜索的時(shí)間復(fù)雜度取決于樹(shù)的高度，最壞情況下（樹(shù)完全不平衡），時(shí)間復(fù)雜度可能會(huì)退化為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;
}

這些搜索算法在不同的場(chǎng)景下有各自的優(yōu)缺點(diǎn)。線性搜索適用于無(wú)序集合，二分搜索適用于有序集合，散列搜索適用于需要快速查找的場(chǎng)景，樹(shù)形結(jié)構(gòu)搜索適用于需要維護(hù)有序數(shù)據(jù)結(jié)構(gòu)的場(chǎng)景。在實(shí)際應(yīng)用中，可以根據(jù)具體需求選擇合適的搜索算法。