前言
在编程领域,数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚给大家分享四种C#中常见的经典查找算法。
-
C#数据结构与算法实战入门指南: C#数据结构与算法实战入门指南
-
欢迎加入DotNetGuide技术社区交流群: 欢迎加入DotNetGuide技术社区交流群
C#二分查找算法
简介
二分查找算法是一种在有序数组中查找特定元素的搜索算法。
-
详细文章描述: C#二分查找算法
代码实现
public class 二分查找算法{/// <summary>/// 二分查找算法/// </summary>/// <param name="arr">arr是已排序的数组</param>/// <param name="target">target是要查找的目标值</param>/// <returns>目标值在数组中的索引,如果未找到则返回-1</returns>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;}}// 未找到 target,返回-1return -1;}public static void BinarySearchRun(){int[] arr = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; //注意:这里的数组是已排序的数组int target = 31; //需要要查找的目标值int result = BinarySearch(arr, target); //调用二分查找方法if (result == -1){Console.WriteLine("元素未找到");}else{Console.WriteLine($"元素找到,索引为:{result},值为:{arr[result]}");}}}
C#线性查找算法
简介
线性查找算法是一种简单的查找算法,用于在一个数组或列表中查找一个特定的元素。它从数组的第一个元素开始,逐个检查每个元素,直到找到所需的元素或搜索完整个数组。线性查找的时间复杂度为O(n),其中n是数组中的元素数量。
-
详细文章描述: C#线性查找算法
代码实现
public static void LinearSearchRun(){int[] arr = { 2, 3, 4, 10, 40, 50, 100, 77, 88, 99 };int target = 100;int result = LinearSearch(arr, target);// 输出结果if (result == -1){Console.WriteLine("元素未找到");}else{Console.WriteLine($"元素在索引 {result} 处找到,index = {result}");}}/// <summary>/// 线性查找函数/// </summary>/// <param name="arr">arr</param>/// <param name="target">target</param>/// <returns></returns>public static int LinearSearch(int[] arr, int target){// 遍历数组for (int i = 0; i < arr.Length; i++){// 如果找到目标值,返回其索引if (arr[i] == target){return i;}}// 如果没有找到,则返回-1return -1;}
C#二叉搜索树算法
简介
二叉搜索树(Binary Search Tree,简称BST)是一种节点有序排列的二叉树数据结构。
-
详细文章描述: C#二叉搜索树算法
代码实现
namespace HelloDotNetGuide.常见算法
{public class 二叉搜索树算法{public static void BinarySearchTreeRun(){var bst = new BinarySearchTree();// 插入一些值到树中bst.Insert(50);bst.Insert(30);bst.Insert(20);bst.Insert(40);bst.Insert(70);bst.Insert(60);bst.Insert(80);bst.Insert(750);Console.WriteLine("中序遍历(打印有序数组):");bst.InorderTraversal();Console.WriteLine("\n");// 查找某些值Console.WriteLine("Search for 40: " + bst.Search(40)); // 输出: TrueConsole.WriteLine("Search for 25: " + bst.Search(25)); // 输出: FalseConsole.WriteLine("\n");// 删除某个值bst.Delete(50);Console.WriteLine("删除50后:");bst.InorderTraversal();}}/// <summary>/// 定义二叉搜索树的节点结构/// </summary>public class TreeNode{public int Value;public TreeNode Left;public TreeNode Right;public TreeNode(int value){Value = value;Left = null;Right = null;}}/// <summary>/// 定义二叉搜索树类/// </summary>public class BinarySearchTree{private TreeNode root;public BinarySearchTree(){root = null;}#region 插入节点/// <summary>/// 插入新值到二叉搜索树中/// </summary>/// <param name="value">value</param>public void Insert(int value){if (root == null){root = new TreeNode(value);}else{InsertRec(root, value);}}private void InsertRec(TreeNode node, int value){if (value < node.Value){if (node.Left == null){node.Left = new TreeNode(value);}else{InsertRec(node.Left, value);}}else if (value > node.Value){if (node.Right == null){node.Right = new TreeNode(value);}else{InsertRec(node.Right, value);}}else{//值已经存在于树中,不再插入return;}}#endregion#region 查找节点/// <summary>/// 查找某个值是否存在于二叉搜索树中/// </summary>/// <param name="value">value</param>/// <returns></returns>public bool Search(int value){return SearchRec(root, value);}private bool SearchRec(TreeNode node, int value){// 如果当前节点为空,表示未找到目标值if (node == null){return false;}// 如果找到目标值,返回trueif (node.Value == value){return true;}// 递归查找左子树或右子树if (value < node.Value){return SearchRec(node.Left, value);}else{return SearchRec(node.Right, value);}}#endregion#region 中序遍历/// <summary>/// 中序遍历(打印有序数组)/// </summary>public void InorderTraversal(){InorderTraversalRec(root);}private void InorderTraversalRec(TreeNode root){if (root != null){InorderTraversalRec(root.Left);Console.WriteLine(root.Value);InorderTraversalRec(root.Right);}}#endregion#region 删除节点/// <summary>/// 删除某个值/// </summary>/// <param name="val">val</param>public void Delete(int val){root = DeleteNode(root, val);}private TreeNode DeleteNode(TreeNode node, int val){if (node == null){return null;}if (val < node.Value){node.Left = DeleteNode(node.Left, val);}else if (val > node.Value){node.Right = DeleteNode(node.Right, val);}else{// 节点有两个子节点if (node.Left != null && node.Right != null){// 使用右子树中的最小节点替换当前节点TreeNode minNode = FindMin(node.Right);node.Value = minNode.Value;node.Right = DeleteNode(node.Right, minNode.Value);}// 节点有一个子节点或没有子节点else{TreeNode? temp = node.Left != null ? node.Left : node.Right;node = temp;}}return node;}/// <summary>/// 找到树中的最小节点/// </summary>/// <param name="node"></param>/// <returns></returns>private TreeNode FindMin(TreeNode node){while (node.Left != null){node = node.Left;}return node;}#endregion}
}
C#哈希查找算法
简介
哈希查找算法是一种高效的查找算法,通过将键值映射到哈希表中的位置来实现快速访问。在C#中,哈希查找通常通过哈希表(Hashtable)或字典(Dictionary)来实现。
-
详细文章描述: C#哈希查找算法
代码实现
public class 哈希查找算法{/// <summary>/// 哈希查找函数/// </summary>/// <param name="target">target</param>public static void HashSearchFunctionRun(int target){//创建一个字典来存储键值对var dic = new Dictionary<int, string>();dic.Add(1, "one");dic.Add(2, "two");dic.Add(3, "three");//查找目标值是否在Dictionary中存在//TryGetValue方法可以返回一个bool值和值,如果找到了目标值,则返回true和对应的值,否则返回false和默认值string value;if (dic.TryGetValue(target, out value)){Console.WriteLine("Found Data: " + value);}else{Console.WriteLine("Not Found Data.");}}}