java之搜索算法

一时失言乱红尘 2024-03-23 13:29 61阅读 0赞

### 算法介绍 ###

>  之前已经介绍了java的排序算法有兴趣的可以看一下  [java之排序算法][java]

###### 搜索算法介绍 ######

Java搜索算法是指在指定查找范围内寻找目标元素的过程。在Java中，通常用于搜索的数据结构包括数组、链表、树等。Java提供了一些常用的搜索算法，如线性搜索、二分搜索、深度优先搜索、广度优先搜索等。

> 1.线性搜索  
>  线性搜索是最简单、最基本的搜索算法之一。它的实现很简单，只需要在查找范围内依次比较每个元素，直到找到目标元素或遍历完整个查找范围。在Java中，通常使用for循环来实现线性搜索。

> 2.二分搜索  
>  二分搜索也称为折半查找，它是一种高效的搜索算法，适用于已排序的查找范围。它的实现思路是首先找到查找范围中间的元素，将其与目标元素进行比较，若相等则返回，若目标元素比中间元素小，则在左半边查找，否则在右半边查找。实现时通常采用递归或循环的方式。

> 3.深度优先搜索  
>  深度优先搜索是一种常用的图搜索算法，在Java中通常用于寻找图的连通分量、最短路径等问题。其实现思路是从任意一个节点开始，沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索下一个路径。实现时通常采用递归的方式。

> 4.广度优先搜索  
> 广度优先搜索也称为宽度优先搜索，是一种图搜索算法，它从距离起点最近的节点开始，逐层向外搜索，直到找到目标节点或搜索完整个图。实现时通常使用队列来保存待搜索的节点。广度优先搜索适用于求解最短路径等问题。

### 搜索算法各类型介绍 ###

##### 一. 顺序搜索（线性搜索) #####

顺序搜索是最简单的搜索算法，它的思路就是从数据集合头部开始，逐个查找每个元素，直到找到目标值或者遍历完整个数据集合。顺序搜索的时间复杂度为O(n)。

以下是一个顺序搜索的Java示例代码：

/**
         *
         * @param arr:要搜索的数组。
         * @param target:要查找的目标值。
         * @return
         */
        public static int linearSearch(int[] arr, int target) {
        
            //遍历整个数组，每次循环检查一个元素。
            for (int i = 0; i < arr.length; i++) {
        
                //检查当前元素是否等于目标值，如果是，则返回该元素的下标。
                if (arr[i] == target)
                    return i;
            }
            //如果循环完整个数组都没有找到目标值，则返回 `-1` 。
            return -1;
        }

##### 二.二分搜索 #####

二分搜索是一种有效的搜索方法，它比顺序搜索更快，基本思路是把数据集合分成两部分，然后在一部分中查找目标值。如果目标值在这部分中，则继续在这部分中查找；否则，在另一部分中查找。重复这个过程直到找到目标值或者确认它不存在。二分搜索的时间复杂度为O(log n)。

以下是一个二分搜索的Java示例代码：

/**
         * @param arr:要搜索的数组。
         * @param target:要查找的目标值。
         * @return
         */
        public static int binarySearch(int[] arr, int target) {
        
            //用于指定搜索范围的数组下标。初始值为数组的第一个和最后一个元素的下标。
            int low = 0, high = arr.length - 1;
            //循环：只要搜索范围不为零，就继续搜索。
            while (low <= high) {
        
                //数组中间值的下标。
                int mid = (low + high) / 2;
                /**
                 * - `if` 语句：检查中间值是否等于目标值，如果是，则返回中间值的下标。
                 * - 如果中间值小于目标值，则缩小搜索范围到右半部分。
                 * - 如果中间值大于目标值，则缩小搜索范围到左半部分。
                 */
                if (arr[mid] == target)
                    return mid;
                else if (arr[mid] < target)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            //循环结束后，如果没有找到目标值，则返回 `-1` 。
            return -1;
        }

##### 三.插值搜索 #####

如果数据分布在一个范围内并且大致均匀，可以使用插值搜索，这是一种基于二分搜索的搜索算法。该算法计算目标值在数列中的位置并在该位置处检查该值，在下一次搜索中，搜索区域被缩小到目标值可能在的那一侧。

以下是一个插值搜索的Java示例代码：

/**
         * @param arr:要搜索的数组
         * @param target:要查找的目标值
         * @return
         */
        public static int interpolationSearch(int[] arr, int target) {
        
            //`low` 和 `high`：用于指定搜索范围的数组下标。初始值为数组的第一个和最后一个元素的下标。
            int low = 0, high = arr.length - 1;
            //`while` 循环：只要搜索范围不为零且目标值在搜索范围内，就继续搜索。
            while (low <= high && target >= arr[low] && target <= arr[high]) {
        
                //`pos`：目标值可能在数列中的位置，根据该位置检查目标值是否在该位置处。
                int pos = low + (high - low) * (target - arr[low]) / (arr[high] - arr[low]);
                /**
                 * - `if` 语句：检查目标值是否在 `pos` 处，如果是，则返回该位置。
                 * - 如果目标值小于 `pos` ，则缩小搜索范围到左半部分。
                 * - 如果目标值大于 `pos` ，则缩小搜索范围到右半部分。
                 */
                if (arr[pos] == target)
                    return pos;
                else if (arr[pos] < target)
                    low = pos + 1;
                else
                    high = pos - 1;
            }
            //循环结束后，如果没有找到目标值，则返回 `-1` 。
            return -1;
        }

##### 四.图搜索 #####

###### 一:广度优先搜索 ######

广度优先搜索（BFS）是一种逐层递进的搜索算法，用于在一个有向或无向图中的所有节点中系统地遍历并检查这些节点。  
 BFS遵循的是一种策略，即从起点开始依次对图中每个未访问过的节点进行广度优先遍历，所以它通常被实现为使用队列的循环。

以下是一个广度优先搜索的Java示例代码：

import java.util.LinkedList;
    import java.util.Queue;
    
    public class BFS {
        
        //marked:一个boolean数组，用于记录是否被访问过。
        private boolean[] marked;
        //edgeTo:一个int数组，用于记录从起点到一个顶点的已知路径上的最后一个顶点。
        private int[] edgeTo;
        //distTo:一个int数组，用于记录从起点到一个顶点的已知路径上的长度。
        private int[] distTo;
        //s:表示起点。
        private final int s;
    
        public BFS(Graph G, int s) {
        
            this.s = s;
            marked = new boolean[G.V()];
            distTo = new int[G.V()];
            edgeTo = new int[G.V()];
            //用于实现BFS搜索。
            bfs(G, s);
        }
    
        private void bfs(Graph G, int s) {
        
            //Queue用于存储顶点，即待处理的顶点。
            Queue<Integer> queue = new LinkedList<>();
            marked[s] = true;
            distTo[s] = 0;
            queue.add(s);
            while (!queue.isEmpty()) {
        
                int v = queue.remove();
                for (int w : G.adj(v)) {
        
                    if (!marked[w]) {
        
                        marked[w] = true;
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        queue.add(w);
                    }
                }
            }
        }
    
        //用于判断是否存在一条从起点到指定顶点v的路径。
        public boolean hasPathTo(int v) {
        
            return marked[v];
        }
    
        //用于返回从起点到指定顶点v的距离。
        public int distTo(int v) {
        
            return distTo[v];
        }
    
        //用于返回从起点到指定顶点v的路径。
        public Iterable<Integer> pathTo(int v) {
        
            if (!hasPathTo(v)) return null;
            LinkedList<Integer> path = new LinkedList<>();
            int x;
            for (x = v; distTo[x] != 0; x = edgeTo[x])
                path.addFirst(x);
            path.addFirst(x);
            return path;
        }
    }

###### 二:深度优先搜索 ######

深度优先搜索（DFS）是一种递归算法，用于在图或树的数据结构中遍历所有节点（或某个特定节点）。  
 在DFS中，我们对一个未搜索过的节点或当前节点的第一个未搜索过的邻居进行深入遍历。然后重复这个过程，直到我们发现一个已经搜索过所有相邻节点的节点。然后我们回溯到前一个节点，并尝试下一个未搜索过的邻居。这个过程一直进行到我们遍历完整个图或树。

以下是一个深度优先搜索的Java示例代码：

import java.util.Stack;
    
    public class DFS {
        
        //marked:一个boolean数组，用于记录是否被访问过。
        private boolean[] marked;
        //edgeTo:一个int数组，用于记录从起点到一个顶点的已知路径上的最后一个顶点。
        private int[] edgeTo;
        //s:表示起点。
        private final int s;
    
        public DFS(Graph G, int s) {
        
            this.s = s;
            marked = new boolean[G.V()];
            edgeTo = new int[G.V()];
            dfs(G, s);
        }
    
        //用于实现DFS搜索。
        private void dfs(Graph G, int v) {
        
            marked[v] = true;
            for (int w : G.adj(v)) {
        
                if (!marked[w]) {
        
                    edgeTo[w] = v;
                    dfs(G, w);
                }
            }
        }
    
        //用于判断是否存在一条从起点到指定顶点v的路径。
        public boolean hasPathTo(int v) {
        
            return marked[v];
        }
    
        //用于返回从起点到指定顶点v的路径。
        public Iterable<Integer> pathTo(int v) {
        
            if (!hasPathTo(v)) return null;
            Stack<Integer> path = new Stack<>();
            for (int x = v; x != s; x = edgeTo[x])
                path.push(x);
            path.push(s);
            return path;
        }
    }

##### 五.哈希搜索 #####

哈希搜索算法是一种使用哈希表来存储数据并快速搜索的算法。在Java中，可以使用HashMap来实现哈希搜索。

以下是一个哈希搜索算法的Java示例代码：

//使用哈希表搜索数组中两数之和等于目标值的情况
        public void hashSearch(int[] nums, int target) {
        
            //创建一个哈希表
            Map<Integer, Integer> map = new HashMap<>();
            //遍历数组
            for (int i = 0; i < nums.length; i++) {
        
                //如果哈希表中存在目标值减当前值的差，则表示找到了结果
                if (map.containsKey(target - nums[i])) {
        
                    System.out.println("找到目标值");
                    return;
                } else {
        
                    //否则将当前值和下标存入哈希表中
                    map.put(nums[i], i);
                }
            }
            //当数组遍历完后仍未找到结果，输出无法找到目标值
            System.out.println("无法找到目标值");
        }

以上代码用来在一个整数数组中查找两数之和等于目标值的情况。首先创建一个HashMap，然后遍历数组，每次判断目标值减去当前值是否存在于HashMap中，如果存在，说明找到了结果，返回；如果不存在，将当前值和下标存入HashMap中，以便后续使用。如果整个数组都被遍历完了仍然没有找到结果，则说明无法找到目标值。

[java]: https://blog.csdn.net/weixin_45300957/article/details/130154376?spm=1001.2014.3001.5502