• 初级查找算法

    文章目录

    1. 顺序查找（Sequential Search）：

    顺序查找是一种简单直接的查找算法，逐个元素依次查找，直到找到目标元素或遍历完整个数据结构。

    举例：假设有一个整数数组arr，我们要查找是否存在目标元素target。

    public class SequentialSearch {
    public static boolean sequentialSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 3;
        boolean result = sequentialSearch(arr, target);
        if (result) {
            System.out.println("目标元素存在");
        } else {
            System.out.println("目标元素不存在");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    2. 二分查找（Binary Search）：

    二分查找是一种针对已排序的数据结构的查找算法，通过将目标元素与中间元素进行比较，不断缩小查找范围，直到找到目标元素或查找范围为空。

    举例：假设有一个有序整数数组arr，我们要查找是否存在目标元素target。

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 3;
        boolean result = binarySearch(arr, target);
        if (result) {
            System.out.println("目标元素存在");
        } else {
            System.out.println("目标元素不存在");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    3. 哈希查找（Hashing）：

    哈希查找通过哈希函数将目标元素映射到数据结构中的位置，以快速定位目标元素。

    方案1 模拟hash底层

    示例：我们首先定义了一个HashNode类来表示哈希表中的节点，每个节点包含一个键和一个值。然后，我们定义了一个HashTable类来实现哈希表的功能。该类使用一个ArrayList来存储桶（每个桶是一个链表），并提供了插入和查找方法。

    在main方法中，我们创建了一个HashTable对象，并向其中插入了几个键值对。然后，我们使用get方法来查找指定键对应的值，并打印结果。

    import java.util.ArrayList;
import java.util.LinkedList;

// 哈希表节点类
class HashNode<K, V> {
    K key;
    V value;

    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

// 哈希表类
class HashTable<K, V> {
    private int maxSize;
    private ArrayList<LinkedList<HashNode<K, V>>> buckets;

    public HashTable(int maxSize) {
        this.maxSize = maxSize;
        buckets = new ArrayList<>(maxSize);

        // 初始化桶
        for (int i = 0; i < maxSize; i++) {
            buckets.add(new LinkedList<>());
        }
    }

    // 哈希函数，计算键的哈希值
    private int getHash(K key) {
        return Math.abs(key.hashCode() % maxSize);
    }

    // 向哈希表中插入键值对
    public void insert(K key, V value) {
        int index = getHash(key);
        LinkedList<HashNode<K, V>> bucket = buckets.get(index);

        // 检查是否已存在相同的键，若存在则更新值
        for (HashNode<K, V> node : bucket) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
        }

        // 若不存在相同的键，则添加新节点
        bucket.add(new HashNode<>(key, value));
    }

    // 从哈希表中查找键对应的值
    public V get(K key) {
        int index = getHash(key);
        LinkedList<HashNode<K, V>> bucket = buckets.get(index);

        // 遍历桶中的节点，查找相应的键值对
        for (HashNode<K, V> node : bucket) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }

        // 若未找到对应的键，则返回null
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建哈希表对象
        HashTable<String, Integer> hashTable = new HashTable<>(10);

        // 向哈希表中插入键值对
        hashTable.insert("apple", 5);
        hashTable.insert("banana", 7);
        hashTable.insert("orange", 3);

        // 查找键对应的值
        System.out.println("apple: " + hashTable.get("apple"));
        System.out.println("banana: " + hashTable.get("banana"));
        System.out.println("orange: " + hashTable.get("orange"));
        System.out.println("grape: " + hashTable.get("grape"));
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    方案2 hash算法章节：

    用数组简单模拟hash原理

    4. 广度优先搜索（Breadth-First Search，BFS）：

    广度优先搜索是一种对于树或图等结构的查找算法，从根节点开始逐层遍历，直到找到目标元素。

    代码实现了广度优先搜索（BFS）算法来查找二叉树中是否存在目标元素。以下是代码的要点：

1. 定义了一个TreeNode类，每个节点有一个整数值，以及左右子节点。
2. 定义了一个bfsSearch方法，接受一个根节点和目标元素作为参数，返回一个boolean值。该方法使用队列来实现广度优先搜索。
3. 在bfsSearch方法中，首先判断根节点是否为空，如果为空则返回false。
4. 创建一个队列，并将根节点加入队列。
5. 当队列非空时，循环执行以下步骤：
   - 弹出队列的第一个节点，并将其值与目标元素进行比较，如果相等则返回true。
   - 如果节点的左子节点不为空，则将左子节点加入队列。
   - 如果节点的右子节点不为空，则将右子节点加入队列。
6. 如果循环结束后仍未找到目标元素，则返回false。
7. 在main方法中创建一个测试用的二叉树，并定义一个目标元素。
8. 调用bfsSearch方法，并根据返回值输出结果。如果返回true，则表示目标元素存在，否则表示目标元素不存在。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    举例：假设有一棵二叉树，我们要查找是否存在目标元素target。

    import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BFS {
    public static boolean bfsSearch(TreeNode root, int target) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == target) {
                return true;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        int target = 3;
        boolean result = bfsSearch(root, target);
        if (result) {
            System.out.println("目标元素存在");
        } else {
            System.out.println("目标元素不存在");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    5. 深度优先搜索（Depth-First Search，DFS）：

    深度优先搜索是一种对于树或图等结构的查找算法，从根节点开始一直遍历到叶子节点，直到找到目标元素或遍历完所有节点。

    方案1 递归实现：

    代码实现了一个深度优先搜索（DFS）算法来搜索给定二叉树中是否存在目标元素。下面是对代码的分析：

1. 定义了一个 `TreeNode` 类，表示二叉树的节点。该类包含一个整数值 `val`，以及左右子节点的引用。

2. 在 `DFS` 类中定义了一个静态方法 `dfsSearch`，用于在给定的二叉树中搜索目标值。该方法的参数包括一个二叉树的根节点 `root` 和目标值 `target`。

3. 在 `dfsSearch` 方法中，首先判断当前节点 `root` 是否为 `null`，如果是则返回 `false`，表示在该子树中不存在目标值。

4. 然后判断当前节点 `root` 的值是否等于目标值 `target`，如果是则返回 `true`，表示目标值存在于该子树中。

5. 如果当前节点不是目标值，则递归调用 `dfsSearch` 方法分别对左子节点和右子节点进行搜索，只要其中一棵子树返回 `true`，即可返回 `true`，表示目标值存在于该子树中。

6. 在 `main` 方法中创建了一个二叉树，并调用 `dfsSearch` 方法来搜索目标值。如果搜索结果为 `true`，则输出 "目标元素存在"，否则输出 "目标元素不存在"。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    举例：假设有一棵二叉树，我们要查找是否存在目标元素target。

    class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class DFS {
    public static boolean dfsSearch(TreeNode root, int target) {
        if (root == null) {
            return false;
        }

        if (root.val == target) {
            return true;
        }
        return dfsSearch(root.left, target) || dfsSearch(root.right, target);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        int target = 3;
        boolean result = dfsSearch(root, target);
        if (result) {
            System.out.println("目标元素存在");
        } else {
            System.out.println("目标元素不存在");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    方案2 栈结构实现：

     - 我们使用一个栈来模拟DFS的过程。
 - 首先将根节点压入栈中，然后进入循环，直到栈为空。
 - 在每次循环中，我们弹出栈顶的节点并进行比较，如果找到目标元素，则返回true。
 - 如果当前节点有右子节点，则将右子节点压入栈中。
 - 如果当前节点有左子节点，则将左子节点压入栈中。
 - 通过不断重复这个过程，直到栈为空或找到目标元素。
 - 如果循环结束仍然没有找到目标元素，则返回false。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class DFS {
    public static boolean dfsSearch(TreeNode root, int target) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node.val == target) {
                return true;
            }

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        int target = 3;
        boolean result = dfsSearch(root, target);
        if (result) {
            System.out.println("目标元素存在");
        } else {
            System.out.println("目标元素不存在");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
  • 相关阅读:
    网络原理之 TCP解释超详细!!!
    小红书商城店铺所有商品接口（整店商品API接口）
    「番外篇」如何用Git平台账号登录建木CI with docker-compose.yml
    刷爆力扣之1 比特与 2 比特字符
    MCAL系列介绍02-WDG（内狗）
    java中main方法和@Test注解的区别
    【python】爬虫记录每小时金价
    MFC程序示例
    单播与多播mac地址
    Pandas实现一列切分为多列
  • 原文地址：https://blog.csdn.net/m0_59076472/article/details/134422624