1. 二分查找（Binary Search）

• 前提条件：数组必须有序。

• 思想：通过不断将查找范围缩小一半来定位目标值。

• 时间复杂度：O(log n)。

• 空间复杂度：O(1)（迭代实现）。

• 适用场景：静态有序数组的查找。

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标值在右半部分
        } else {
            right = mid - 1; // 目标值在左半部分
        }
    }
    return -1; // 未找到
}

2. 哈希查找（Hash Search）

• 前提条件：数据存储在哈希表中。

• 思想：通过哈希函数将键映射到存储位置，直接访问目标值。

• 时间复杂度：

  • 平均情况：O(1)。

  • 最坏情况（哈希冲突严重）：O(n)。

• 空间复杂度：O(n)（存储哈希表）。

• 适用场景：快速查找，适合键值对存储。

import java.util.HashMap;

public static int hashSearch(HashMap<Integer, Integer> map, int target) {
    if (map.containsKey(target)) {
        return map.get(target); // 返回目标值
    }
    return -1; // 未找到
}

// 示例用法
public static void main(String[] args) {
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(1, 100);
    map.put(2, 200);
    map.put(3, 300);
    int result = hashSearch(map, 2); // 查找键为 2 的值
    System.out.println(result); // 输出 200
}

3. 二叉树查找（Binary Search Tree, BST）

• 前提条件：数据存储在二叉搜索树中（左子树 < 根节点 < 右子树）。

• 思想：通过递归或迭代在二叉搜索树中查找目标值。

• 时间复杂度：

  • 平均情况：O(log n)。

  • 最坏情况（树退化为链表）：O(n)。

• 空间复杂度：

  • 递归实现：O(log n)（栈空间）。

  • 迭代实现：O(1)。

• 适用场景：动态数据集，支持插入、删除和查找。

二叉搜索树节点定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

递归实现

public static TreeNode bstSearch(TreeNode root, int target) {
    if (root == null || root.val == target) {
        return root; // 找到目标节点或未找到
    }
    if (target < root.val) {
        return bstSearch(root.left, target); // 在左子树中查找
    } else {
        return bstSearch(root.right, target); // 在右子树中查找
    }
}

迭代实现

public static TreeNode bstSearchIterative(TreeNode root, int target) {
    while (root != null && root.val != target) {
        if (target < root.val) {
            root = root.left; // 在左子树中查找
        } else {
            root = root.right; // 在右子树中查找
        }
    }
    return root; // 找到目标节点或未找到
}

总结对比

选择建议

1. 静态有序数据：二分查找（效率高，实现简单）。

2. 动态数据集：二叉搜索树（支持插入、删除和查找）。

3. 快速查找键值对：哈希查找（平均时间复杂度最优）。

示例代码整合

public class SearchAlgorithms {
    public static void main(String[] args) {
        // 二分查找示例
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int index = binarySearch(arr, target);
        System.out.println("二分查找结果：" + index);

        // 哈希查找示例
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1, 100);
        map.put(2, 200);
        map.put(3, 300);
        int value = hashSearch(map, 2);
        System.out.println("哈希查找结果：" + value);

        // 二叉树查找示例
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        TreeNode node = bstSearch(root, 5);
        System.out.println("二叉树查找结果：" + (node != null ? node.val : "未找到"));
    }

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

    // 哈希查找
    public static int hashSearch(HashMap<Integer, Integer> map, int target) {
        if (map.containsKey(target)) {
            return map.get(target);
        }
        return -1;
    }

    // 二叉树查找（递归）
    public static TreeNode bstSearch(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (target < root.val) {
            return bstSearch(root.left, target);
        } else {
            return bstSearch(root.right, target);
        }
    }
}