Java中的搜索算法函数及实现

Java中有许多搜索算法，包括线性搜索、二分搜索、广度优先搜索、深度优先搜索等。这些算法通常都涉及到对列表、数组、图等数据结构的遍历和搜索，帮助我们在大量数据中快速找到所需的值或路径。

线性搜索

线性搜索是最简单的搜索算法之一，也被称为顺序搜索。它顺序查找列表或数组中的每个元素，直到找到匹配的元素或搜索完整个列表。Java中的线性搜索函数适用于任何类型的列表或数组。

Java代码示例：

public static int linearSearch(int[] arr, int x) {
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == x) {
            return i;
        }
    }
    return -1;
}

二分搜索

二分搜索也称为折半查找，是在已排序的数组或列表中查找某个元素的算法。它通过将搜索区域分为两个部分，比较中间元素与所需元素的大小，来缩小搜索范围。如果需要查找的元素小于中间值则在左侧查找，否则在右侧查找。这个过程一直持续到找到所需元素或搜索区域缩小到空集。

Java代码示例：

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

广度优先搜索

广度优先搜索（BFS）是图形搜索算法，通过先遍历所有相邻节点，然后依次遍历下一层节点，从而查找所需值或路径。在 Java 中，BFS 常常用于树和图的遍历或寻找最短路径。

Java代码示例：

public static void bfs(int start, int[][] graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.length];
    visited[start] = true;
    queue.offer(start);
    while(!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for(int i = 0; i < graph[node].length; i++) {
            int nextNode = graph[node][i];
            if(!visited[nextNode]) {
                visited[nextNode] = true;
                queue.offer(nextNode);
            }
        }
    }
}

深度优先搜索

深度优先搜索（DFS）是另一种图形搜索算法，通过访问一个节点后立即递归到相邻未被访问的节点，直到找到所需值或全部节点被访问。在 Java 中，DFS 常用于图形中的深度遍历。

Java代码示例：

public static void dfs(int start, boolean[] visited, int[][] graph) {
    visited[start] = true;
    System.out.print(start + " ");
    for(int i = 0; i < graph[start].length; i++) {
        int nextNode = graph[start][i];
        if(!visited[nextNode]) {
            dfs(nextNode, visited, graph);
        }
    }
}