C#二分查找详解（从前提条件到递归实现）

二、二分查找的基本思想

二分查找的核心思想是“分而治之”：每次将搜索区间缩小一半，直到找到目标值或区间为空。

具体步骤如下：

• 设定左边界 left = 0，右边界 right = 数组长度 - 1。
• 计算中间位置 mid = (left + right) / 2。
• 比较 arr[mid] 与目标值 target：
• 若相等，则找到目标，返回索引。
• 若 arr[mid] < target，说明目标在右半部分，更新 left = mid + 1。
• 若 arr[mid] > target，说明目标在左半部分，更新 right = mid - 1。
• 重复上述过程，直到 left > right，此时表示未找到目标。

三、递归实现二分查找（C#代码）

下面是一个完整的 C# 递归实现二分查找的示例。该方法适用于已排序的整数数组。

public static int BinarySearchRecursive(int[] arr, int target, int left, int right){    // 基本情况：未找到目标    if (left > right)    {        return -1;    }    // 计算中间索引（防止溢出）    int mid = left + (right - left) / 2;    // 找到目标    if (arr[mid] == target)    {        return mid;    }    // 目标在左半部分    if (arr[mid] > target)    {        return BinarySearchRecursive(arr, target, left, mid - 1);    }    // 目标在右半部分    else    {        return BinarySearchRecursive(arr, target, mid + 1, right);    }}// 调用示例static void Main(){    int[] sortedArray = { 1, 3, 5, 7, 9, 11, 13 };    int target = 7;    int result = BinarySearchRecursive(sortedArray, target, 0, sortedArray.Length - 1);    if (result != -1)    {        Console.WriteLine($"目标 {target} 在索引 {result} 处找到。");    }    else    {        Console.WriteLine($"目标 {target} 未找到。");    }}

四、注意事项与常见错误

在实现递归二分查找时，新手常犯以下错误：

• 忘记递归终止条件：必须确保当 left > right 时返回 -1，否则会导致无限递归甚至栈溢出。
• 中间索引计算溢出：虽然 C# 中 (left + right) / 2 通常安全，但在极端情况下建议使用 left + (right - left) / 2 避免整数溢出。
• 数组未排序：这是最常见的错误。务必确保输入数组是有序的，否则结果不可预测。

五、总结

通过本文，你已经掌握了 C#二分查找 的核心前提、基本逻辑和递归实现二分查找的方法。记住，二分查找的时间复杂度为 O(log n)，远优于线性查找的 O(n)，但前提是数据必须有序。

希望这篇C#算法教程能帮助你打下坚实的算法基础。动手写一写代码，加深理解吧！

© 2023 C# 算法学习指南 | 专注 二分查找前提条件 与实战教学