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;
}

这些搜索算法在不同的场景下有各自的优缺点。线性搜索适用于无序集合，二分搜索适用于有序集合，散列搜索适用于需要快速查找的场景，树形结构搜索适用于需要维护有序数据结构的场景。在实际应用中，可以根据具体需求选择合适的搜索算法。