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
}
算法思路
- 定义了左右两个指针，分别指向数组的头和尾。
- 不断将数组分成两半，直到找到目标值为止。在每一次迭代中，我们通过计算中间值来判断目标值在左半边还是右半边。如果目标值等于中间值，那么我们就找到了目标值的索引。如果目标值小于中间值，那么我们就在左半边继续查找。如果目标值大于中间值，那么我们就在右半边继续查找。
- 根据匹配策略返回目标值的索引或者最接近目标值的索引。
测试结果
测试代码如下：
/// <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);
}
执行结果如下：
结束语
通过本章的代码可以轻松实现二分查找算法。如果您觉得本文对您有所帮助，请不要吝啬您的点赞和评论，提供宝贵的反馈和建议，让更多的读者受益。
