经典查找算法详解：线性、二分、BST、哈希、索引

1. 线性查找

线性查找适用于未排序或已排序的数据集。该算法通过逐一比较数组中的每个元素来寻找目标值，直至找到匹配项或遍历完整个数组。其时间复杂度为O(n)，其中n为数组长度。

public static int linearSearch(int[] arr, int target) { for (int i = 0; i 

2. 二分查找

二分查找要求数据集必须是有序的。算法首先检查数组中间的元素，如果它不是目标值且数组不为空，则根据目标值与中间值的大小关系决定是在前半部分还是后半部分继续搜索。此过程重复进行，每次都将搜索区间减半，直至找到目标值或确定不存在。时间复杂度为O(log n)。

public static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] 

3. 二叉搜索树查找

二叉搜索树（BST）是一种特殊的二叉树结构，其中每个节点的左子树仅包含比该节点小的值，而右子树仅包含更大的值。查找操作从根节点开始，若当前节点非空且其值不等于目标值，则根据大小关系递归地在左子树或右子树中继续查找。理想情况下，时间复杂度接近O(log n)。

public static TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) return root; return val 

4. 哈希查找

哈希查找利用哈希表实现快速查找，通过哈希函数将关键字映射到表中的一个位置，从而直接访问存储的数据。理想状态下，查找时间为常数级O(1)，但在存在哈希碰撞时，实际性能会有所下降。

5. 索引查找

索引查找是线性查找和二分查找的结合体，通过预先构建的索引来加速查找过程。数据被分成若干块，每块内部不一定有序，但块与块之间保持有序。首先使用二分查找定位到合适的块，然后在块内执行线性查找。这种方法的时间复杂度介于O(n)和O(log n)之间，具体取决于块的大小和数量。