C# | 二分查找算法的实现

简介: 二分查找法一种在**有序数组**中查找目标值的算法。划重点——“**有序**”,与需要遍历整个数组的查询算法不同,二分查找法通过将数组分成两部分来快速定位目标值所在的位置。它的主要好处在于它的效率很高。因为它能够通过每次排除一半的元素来快速缩小搜索范围,因此在大型数据集上使用二分查找法可以显著提高查找速度。

image.png

在这里插入图片描述

C# | 二分查找算法的实现

@[toc]

前言

二分查找法一种在有序数组中查找目标值的算法。划重点——“有序”,与需要遍历整个数组的查询算法不同,二分查找法通过将数组分成两部分来快速定位目标值所在的位置。

  • 二分查找法有什么用呢?
    它的主要好处在于它的效率很高。因为它能够通过每次排除一半的元素来快速缩小搜索范围,因此在大型数据集上使用二分查找法可以显著提高查找速度。

  • 比较一下二分查找法和其他常见的查找算法的效率。
    相比于顺序查找法,它的平均时间复杂度更低,可以达到O(log n)。而对于哈希表查找法,虽然哈希表可以在O(1)的时间内查找目标值,但是哈希表需要额外的空间来存储哈希函数和冲突处理,而且哈希表在处理数据集较小的情况下效率不如二分查找法。

示例代码

现在来看一下C#中的二分查找算法是如何实现的:

        /// <summary>
        /// 二分法查找目标值在数组中的索引(值的比较由回调完成,不提供目标值)
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array">数据集合</param>
        /// <param name="comparer">比较回调</param>
        /// <param name="strategy">匹配策略,如果是完全匹配策略,则若没有相等的则返回-1,若策略是匹配不到时采用较小值,则返回最接近的前一个值,若策略是匹配不到时采用较大值,则返回最接近的后一个值</param>
        /// <returns></returns>
        public static int BinarySearch<T>(T[] array, Func<T, ComparisonResult> comparer, MatchStrategy strategy)
        {
   
   
            int left = 0;
            int right = array.Length - 1;
            int result = -1;

            while (left <= right)
            {
   
   
                int mid = left + (right - left) / 2;
                ComparisonResult comparison = comparer(array[mid]);

                if (comparison == ComparisonResult.Equal)
                {
   
   
                    result = mid;
                    break;
                }
                else if (comparison == ComparisonResult.Less)
                {
   
   
                    left = mid + 1;
                }
                else
                {
   
   
                    right = mid - 1;
                }
            }

            if (result != -1)
            {
   
   
                return result;
            }
            else if (strategy == MatchStrategy.ExactMatch)
            {
   
   
                return -1;
            }
            else if (strategy == MatchStrategy.LowerBound)
            {
   
   
                if (right < 0)
                {
   
   
                    return -1;
                }
                else
                {
   
   
                    return right;
                }
            }
            else // strategy == MatchStrategy.UpperBound
            {
   
   
                if (left >= array.Length)
                {
   
   
                    return -1;
                }
                else
                {
   
   
                    return left;
                }
            }
        }

这段代码实现了一个泛型的二分查找法,可以适用于任何数据类型。通过传递一个比较回调函数和一个匹配策略,我们可以在数组中查找目标值的索引。

补充一下,关于示例中使用到的ComparisonResult枚举类型和MatchStrategy枚举类型的源代码如下:

    public enum ComparisonResult
    {
   
   
        Less = -1,
        Equal = 0,
        Greater = 1,
    }

    public enum MatchStrategy
    {
   
   
        ExactMatch,
        LowerBound,
        UpperBound
    }

算法思路

  1. 定义了左右两个指针,分别指向数组的头和尾。
  2. 不断将数组分成两半,直到找到目标值为止。在每一次迭代中,我们通过计算中间值来判断目标值在左半边还是右半边。如果目标值等于中间值,那么我们就找到了目标值的索引。如果目标值小于中间值,那么我们就在左半边继续查找。如果目标值大于中间值,那么我们就在右半边继续查找。
  3. 根据匹配策略返回目标值的索引或者最接近目标值的索引。

测试结果

测试代码如下:

        /// <summary>
        /// 测试BinarySearch方法在数组中查找一个存在的元素时能够正确返回其索引值。
        /// </summary>
        [TestMethod]
        public void TestBinarySearch_ExistingElement_ReturnsCorrectIndex()
        {
   
   
            // Arrange
            int[] array = {
   
    1, 3, 5, 7, 9 };
            Func<int, ComparisonResult> comparer = x => x.CompareTo(5) switch
            {
   
   
                -1 => ComparisonResult.Less,
                0 => ComparisonResult.Equal,
                _ => ComparisonResult.Greater
            };
            MatchStrategy strategy = MatchStrategy.ExactMatch;

            // Act
            int result = Dichotomy.BinarySearch(array, comparer, strategy);

            // Assert
            Assert.AreEqual(2, result);
        }

执行结果如下:
image.png

结束语

通过本章的代码可以轻松实现二分查找算法。如果您觉得本文对您有所帮助,请不要吝啬您的点赞和评论,提供宝贵的反馈和建议,让更多的读者受益。

相关文章
|
7天前
|
算法 索引
【算法】——二分查找合集
二分查找基础模版和进阶模版,查找元素位置,搜索插入位置,x的平方根,山脉数组的峰顶索引,寻找峰值,点名
|
5天前
|
存储 监控 算法
企业内网监控系统中基于哈希表的 C# 算法解析
在企业内网监控系统中,哈希表作为一种高效的数据结构,能够快速处理大量网络连接和用户操作记录,确保网络安全与效率。通过C#代码示例展示了如何使用哈希表存储和管理用户的登录时间、访问IP及操作行为等信息,实现快速的查找、插入和删除操作。哈希表的应用显著提升了系统的实时性和准确性,尽管存在哈希冲突等问题,但通过合理设计哈希函数和冲突解决策略,可以确保系统稳定运行,为企业提供有力的安全保障。
|
2月前
|
算法 C#
C#常见的四种经典查找算法
C#常见的四种经典查找算法
|
2月前
|
算法 C# 索引
C#线性查找算法
C#线性查找算法!
|
3月前
|
存储 算法 C#
C#哈希查找算法
C#哈希查找算法
|
3月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
3月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
3月前
|
消息中间件 存储 算法
一文搞懂二分查找算法!
一文搞懂二分查找算法!
138 0
|
3月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
36 0
|
3月前
|
机器学习/深度学习 算法 数据挖掘
使用C# 实现期望最大化算法
使用C# 实现期望最大化算法
58 0