C#常见的四种经典查找算法

简介: C#常见的四种经典查找算法

前言

在编程领域,数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚给大家分享四种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,返回-1
            return -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是数组中的元素数量。

代码实现

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;
                }
            }
            // 如果没有找到,则返回-1
            return -1;
        }

C#二叉搜索树算法

简介

二叉搜索树(Binary Search Tree,简称BST)是一种节点有序排列的二叉树数据结构。

代码实现

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)); // 输出: True
            Console.WriteLine("Search for 25: " + bst.Search(25)); // 输出: False
            Console.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;
            }
            // 如果找到目标值,返回true
            if (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)来实现。

代码实现

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.");
            }
        }
    }
相关文章
|
10月前
|
开发框架 算法 搜索推荐
C# .NET面试系列九:常见的算法
#### 1. 求质数 ```c# // 判断一个数是否为质数的方法 public static bool IsPrime(int number) { if (number < 2) { return false; } for (int i = 2; i <= Math.Sqrt(number); i++) { if (number % i == 0) { return false; } } return true; } class Progr
147 1
|
10月前
|
搜索推荐 算法 C#
【Unity 3D】C#中冒泡排序、选择排序、插入排序等算法的详解(附源码 超详细)
【Unity 3D】C#中冒泡排序、选择排序、插入排序等算法的详解(附源码 超详细)
180 1
|
8天前
|
缓存 监控 算法
基于 C# 网络套接字算法的局域网实时监控技术探究
在数字化办公与网络安全需求增长的背景下,局域网实时监控成为企业管理和安全防护的关键。本文介绍C#网络套接字算法在局域网实时监控中的应用,涵盖套接字创建、绑定监听、连接建立和数据传输等操作,并通过代码示例展示其实现方式。服务端和客户端通过套接字进行屏幕截图等数据的实时传输,保障网络稳定与信息安全。同时,文章探讨了算法的优缺点及优化方向,如异步编程、数据压缩与缓存、错误处理与重传机制,以提升系统性能。
32 2
|
2月前
|
缓存 算法 安全
剖析‘共享文件夹只让指定用户看到’的 C# 精妙算法
在数字化时代,信息精准共享与管控至关重要。基于角色的访问控制(RBAC)算法通过将用户划分为不同角色并分配权限,确保“共享文件夹只让指定用户看到”。本文以C#代码为例,展示如何实现这一目标,并探讨大规模应用中的动态变更、性能优化和安全性挑战。RBAC算法结合C#编程,助力高效、安全的协作环境。
|
3月前
|
存储 监控 算法
企业内网监控系统中基于哈希表的 C# 算法解析
在企业内网监控系统中,哈希表作为一种高效的数据结构,能够快速处理大量网络连接和用户操作记录,确保网络安全与效率。通过C#代码示例展示了如何使用哈希表存储和管理用户的登录时间、访问IP及操作行为等信息,实现快速的查找、插入和删除操作。哈希表的应用显著提升了系统的实时性和准确性,尽管存在哈希冲突等问题,但通过合理设计哈希函数和冲突解决策略,可以确保系统稳定运行,为企业提供有力的安全保障。
|
4月前
|
算法 C# 索引
C#线性查找算法
C#线性查找算法!
|
5月前
|
存储 算法 C#
C#哈希查找算法
C#哈希查找算法
|
5月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
5月前
|
机器学习/深度学习 算法 数据挖掘
使用C# 实现期望最大化算法
使用C# 实现期望最大化算法
81 0
|
6月前
|
存储 算法 C#
C#二叉搜索树算法
C#二叉搜索树算法