深入理解與實(shí)現(xiàn)：常見搜索算法的Java示例

搜索算法是計(jì)算機(jī)科學(xué)中的基本概念，用于在數(shù)據(jù)集合中查找特定元素或解決問題。本文將深入介紹二分查找、深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）這三種常見的搜索算法，并提供詳細(xì)的Java代碼示例。

1. 二分查找（Binary Search）

概念：二分查找是一種高效的搜索算法，前提是數(shù)據(jù)集合已排序。該算法將待查找的范圍逐步縮小至目標(biāo)元素，減少搜索時(shí)間復(fù)雜度。

代碼示例：

public?class?BinarySearchExample?{

????public?static?int?binarySearch(int[]?array,?int?target)?{
????????int?left?=?0;
????????int?right?=?array.length?-?1;

????????while?(left?<=?right)?{
????????????int?mid?=?left?+?(right?-?left)?/?2;

????????????if?(array[mid]?==?target)?{
????????????????return?mid;
????????????}?else?if?(array[mid]?<?target)?{
????????????????left?=?mid?+?1;
????????????}?else?{
????????????????right?=?mid?-?1;
????????????}
????????}

????????return?-1;?//?目標(biāo)元素不存在
????}

????public?static?void?main(String[]?args)?{
????????int[]?sortedArray?=?{2,?5,?8,?12,?16,?23,?38,?56,?72,?91};
????????int?target?=?23;

????????int?result?=?binarySearch(sortedArray,?target);
????????if?(result?!=?-1)?{
????????????System.out.println("目標(biāo)元素?"?+?target?+?"?在索引?"?+?result?+?"?處找到。");
????????}?else?{
????????????System.out.println("目標(biāo)元素?"?+?target?+?"?不存在于數(shù)組中。");
????????}
????}
}


2. 深度優(yōu)先搜索（DFS）

概念：深度優(yōu)先搜索是一種遍歷圖或樹的算法，它首先沿著一條路徑盡可能深地訪問，然后回溯并探索其他分支。

代碼示例：

import?java.util.LinkedList;

class?GraphDFS?{
????private?int?V;?//?節(jié)點(diǎn)數(shù)
????private?LinkedList<Integer>[]?adj;?//?鄰接表

????public?GraphDFS(int?vertices)?{
????????V?=?vertices;
????????adj?=?new?LinkedList[V];
????????for?(int?i?=?0;?i?<?V;?i++)?{
????????????adj[i]?=?new?LinkedList<>();
????????}
????}

????//?添加邊
????public?void?addEdge(int?v,?int?w)?{
????????adj[v].add(w);
????}

????void?dfs(int?v,?boolean[]?visited)?{
????????visited[v]?=?true;
????????System.out.print(v?+?"?");

????????for?(int?neighbor?:?adj[v])?{
????????????if?(!visited[neighbor])?{
????????????????dfs(neighbor,?visited);
????????????}
????????}
????}

????void?DFS(int?start)?{
????????boolean[]?visited?=?new?boolean[V];
????????dfs(start,?visited);
????}

????public?static?void?main(String[]?args)?{
????????GraphDFS?graph?=?new?GraphDFS(7);
????????graph.addEdge(0,?1);
????????graph.addEdge(0,?2);
????????graph.addEdge(1,?3);
????????graph.addEdge(1,?4);
????????graph.addEdge(2,?5);
????????graph.addEdge(2,?6);

????????System.out.println("深度優(yōu)先遍歷:");
????????graph.DFS(0);
????}
}


3. 廣度優(yōu)先搜索（BFS）

概念：廣度優(yōu)先搜索也用于遍歷圖或樹，它首先訪問起始節(jié)點(diǎn)的所有鄰居，然后逐層擴(kuò)展。

代碼示例：

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

class?GraphBFS?{
????private?int?V;?//?節(jié)點(diǎn)數(shù)
????private?LinkedList<Integer>[]?adj;?//?鄰接表

????public?GraphBFS(int?vertices)?{
????????V?=?vertices;
????????adj?=?new?LinkedList[V];
????????for?(int?i?=?0;?i?<?V;?i++)?{
????????????adj[i]?=?new?LinkedList<>();
????????}
????}

????//?添加邊
????public?void?addEdge(int?v,?int?w)?{
????????adj[v].add(w);
????}

????void?BFS(int?start)?{
????????boolean[]?visited?=?new?boolean[V];
????????Queue<Integer>?queue?=?new?LinkedList<>();

????????visited[start]?=?true;
????????queue.add(start);

????????while?(!queue.isEmpty())?{
????????????int?v?=?queue.poll();
????????????System.out.print(v?+?"?");

????????????for?(int?neighbor?:?adj[v])?{
????????????????if?(!visited[neighbor])?{
????????????????????visited[neighbor]?=?true;
????????????????????queue.add(neighbor);
????????????????}
????????????}
????????}
????}

????public?static?void?main(String[]?args)?{
????????GraphBFS?graph?=?new?GraphBFS(7);
????????graph.addEdge(0,?1);
????????graph.addEdge(0,?2);
????????graph.addEdge(1,?3);
????????graph.addEdge(1,?4);
????????graph.addEdge(2,?5);
????????graph.addEdge(2,?6);

????????System.out.println("廣度優(yōu)先遍歷:");
????????graph.BFS(0);
????}
}


本文深入探討了二分查找、深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）這三種常見的搜索算法。通過詳細(xì)的Java代碼示例和解釋，我們希望您能更好地理解這些算法的原理和應(yīng)用。

希望本文對(duì)您理解搜索算法有所幫助。如果您對(duì)其他算法也感興趣，歡迎繼續(xù)探索和學(xué)習(xí)！