java-搜索算法

搜索算法：

线性搜索（Linear Search）
二分搜索（Binary Search）
深度优先搜索（Depth-First Search, DFS）
广度优先搜索（Breadth-First Search, BFS）

1. 线性搜索（Linear Search）

意义：
线性搜索是一种简单的搜索算法，它从头到尾遍历数组，检查每个元素是否为目标值。如果找到目标值，则返回其索引；如果遍历完整个数组都没有找到，则返回一个表示未找到的值（通常是-1）。

Java案例：

public class LinearSearch {public static int linearSearch(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i; // 找到目标，返回索引}}return -1; // 未找到目标，返回-1}public static void main(String[] args) {int[] arr = {3, 5, 2, 4, 9};int target = 4;int index = linearSearch(arr, target);if (index != -1) {System.out.println("Element found at index: " + index);} else {System.out.println("Element not found.");}}
}

2. 二分搜索（Binary Search）

意义：
二分搜索是一种在已排序数组中查找特定元素的搜索算法。它通过比较数组中间的元素与目标值来工作，如果中间元素与目标值相等，则搜索成功；如果目标值小于中间元素，则在数组的左半部分继续搜索；如果目标值大于中间元素，则在数组的右半部分继续搜索。这个过程重复进行，直到找到目标值或搜索范围为空。

Java案例：

public class BinarySearch {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; // 未找到目标，返回-1}public static void main(String[] args) {int[] arr = {2, 3, 4, 10, 40};int target = 10;int index = binarySearch(arr, target);if (index != -1) {System.out.println("Element found at index: " + index);} else {System.out.println("Element not found.");}}
}

3. 深度优先搜索（Depth-First Search, DFS）

意义：
深度优先搜索是一种用于遍历或搜索树或图的算法。它从一个节点开始，尽可能深地搜索树的分支。在图的遍历中，DFS会访问一个节点，然后沿着一条边走到下一个节点，然后继续深入，直到到达没有未访问邻居的节点，然后回溯。

Java案例（使用递归实现图的DFS遍历）：

public class DFS {private boolean[] visited;private int[] graph;public DFS(int[][] graph) {this.graph = new int[graph.length];for (int[] row : graph) {for (int item : row) {this.graph[item] = item;}}visited = new boolean[graph.length];}public void dfs(int vertex) {visited[vertex] = true;System.out.print(vertex + " ");for (int i = 0; i < graph.length; i++) {if (graph[vertex] == i && !visited[i]) {dfs(i);}}}public static void main(String[] args) {int[][] graph = {{1, 2}, {0, 3}, {0, 4}, {1, 5}, {1, 2}};DFS dfs = new DFS(graph);dfs.dfs(0); // 从节点0开始遍历}
}

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

意义：
广度优先搜索也是一种用于遍历或搜索树或图的算法。与DFS不同，BFS从一个节点开始，首先访问所有相邻的节点，然后再逐层向外扩展。

Java案例（使用队列实现图的BFS遍历）：

import java.util.LinkedList;
import java.util.Queue;public class BFS {private boolean[] visited;private int[][] graph;public BFS(int[][] graph) {this.graph = graph;visited = new boolean[graph.length];}public void bfs(int startNode) {Queue<Integer> queue = new LinkedList<>();visited[startNode] = true;queue.add(startNode);while (!queue.isEmpty()) {int currentNode = queue.poll();System.out.print(currentNode + " ");for (int neighbor : graph[currentNode]) {if (!visited[neighbor]) {visited[neighbor] = true;queue.add(neighbor);}}}}public static void main(String[] args) {int[][] graph = {{1, 2}, {0, 3}, {0, 4}, {1, 5}, {1, 2}};BFS bfs = new BFS(graph);bfs.bfs(0); // 从节点0开始遍历}
}