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开始遍历
}
}
这些案例展示了不同搜索算法的基本实现和应用场景。线性搜索和二分搜索主要用于数组的搜索，而深度优先搜索和广度优先搜索则用于图或树的遍历。每种算法都有其特定的应用场景和优势。
原文地址：https://blog.csdn.net/weixin_44372802/article/details/143922154
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！