C# 二分查找算法实现与原理详解

算法原理与性能特征

折半搜索（Binary Search），也称为二分查找算法或二分搜索，是一种高效的查找技术，专门用于在有序数组中定位特定元素。其核心思想是将搜索范围一分为二，从而快速排除一半的无关数据。

搜索过程遵循以下逻辑：

1. 初始比较：从数组的中间元素开始，检查它是否等于目标值。若相等，则查找成功并返回索引。
2. 区间缩减：如果目标值小于中间元素，说明目标只可能存在于左半部分；若大于中间元素，则存在于右半部分。接着在选定的一半区域中，再次从中间元素开始比较。
3. 终止条件：如果在某一步骤中，搜索区间为空（即下标越界），则代表数组中不存在该元素，查找结束。

由于每次比较都能将搜索区域减少一半，二分查找具有极高的效率。其时间复杂度为：

其中 n 代表集合中元素的个数。这意味着即使面对百万级数据，只需约 20 次比较即可完成查找。同时，基于递归实现且无额外数据结构占用的情况下，其空间复杂度通常视为：

C# 递归实现代码

以下是使用 C# 编写的二分查找递归函数。该函数接收整数数组、起始索引、结束索引以及目标键值作为参数，返回目标值的索引位置，若未找到则返回 -1。

/// <summary>
/// 递归实现二分查找
/// </summary>
/// <param name="arr">已排序的目标数组</param>
/// <param name="low">搜索区间的起始索引（通常为0）</param>
/// <param name="high">搜索区间的结束索引</param>
/// <param name="key">要查找的目标元素</param>
/// <returns>找到返回索引，未找到返回-1</returns>
public static int BinarySearch(int[] arr, int low, int high, int key)
{
    // 基准情况：如果起始索引大于结束索引，说明区间为空
    if (low > high)
        return -1;

    // 计算中间索引
    int mid = (low + high) / 2;

    // 判断中间元素与目标值的关系
    if (arr[mid] == key)
        return mid;              // 找到目标，返回索引
    else if (arr[mid] > key)
        return BinarySearch(arr, low, mid - 1, key);  // 目标在左半区，递归查找左侧
    else
        return BinarySearch(arr, mid + 1, high, key); // 目标在右半区，递归查找右侧
}

代码运行示例

为了验证上述算法的有效性，我们可以构建一个有序整型数组进行调用测试。以下实例在包含 1 到 13 的数组中查找数字 13：

int[] y = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13};
int rr = BinarySearch(y, 0, y.Length - 1, 13);
Console.Write(rr);  // 输出结果: 12

在该示例中，数组长度为 13，最后索引为 12。由于数组是有序的且最后一个元素正是我们要找的 13，最终返回的索引值为 12。

以上就是 C# 二分查找算法的详细实现与原理分析，更多关于 C# 基础算法的资料请关注本站其它相关文章！