C# 中的二分查找法 - 初学者指南

二分查找（Binary Search）是一种高效的查找算法，它比顺序查找快得多，但有一个重要前提：数据必须是有序的。

1. 核心思想：猜数字游戏

想象一下猜数字游戏：我心中想一个1-100之间的数字，你每次猜一个数，我会告诉你"大了"、"小了"还是"对了"。

最聪明的策略：总是猜中间的数！

• 第一次猜50

• 如果我说"大了"，你就猜25（1-50的中间）

• 如果我说"小了"，你就猜75（50-100的中间）

这样每次都能排除一半的可能性！这就是二分查找的核心思想。

2. 算法步骤详解

假设我们在有序数组 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找 23：

1. 确定范围：开始时，整个数组都是查找范围

   • 左边界 left = 0（第一个元素）

   • 右边界 right = 9（最后一个元素）

2. 计算中间位置：mid = (0 + 9) / 2 = 4（取整）

   • 中间值 arr[4] = 16

   • 目标值 23 > 16，所以在右半部分继续查找

3. 调整范围：左边界移动到 mid + 1 = 5

   • 新范围：索引 5 到 9

   • 新中间：mid = (5 + 9) / 2 = 7

   • 中间值 arr[7] = 45

   • 目标值 23 < 45，所以在左半部分继续查找

4. 继续查找：右边界移动到 mid - 1 = 6

   • 新范围：索引 5 到 6

   • 新中间：mid = (5 + 6) / 2 = 5

   • 中间值 arr[5] = 23 ← 找到了！

3. C# 代码实现

迭代版本（推荐初学者使用）

static int FindNum(int[] array,int number)
    {
        int firstIndex = 0;
        int lastIndex = array.Length - 1;
        
        while (firstIndex <= lastIndex)
        {
            int middleIndex = firstIndex + (lastIndex - firstIndex) / 2;
            if (number == array[middleIndex]) return middleIndex;
            else if (number > array[middleIndex])
            {
                firstIndex = middleIndex + 1;
            }
            else
            {
                lastIndex = middleIndex - 1;
            }
        }
        return -1;
    }
    static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Console.WriteLine(string.Join(",",arr));
        Console.Write("请输入一个你要查找的数：");
        int n = Convert.ToInt32(Console.ReadLine());
        int result = FindNum(arr, n);
        Console.WriteLine(result);
    }

递归版本（了解即可）

// 二分查找方法 - 递归版本
static int BinarySearchRecursive(int[] array, int target, int left, int right)
{
    if (left > right)
    {
        return -1;  // 基础情况：没找到
    }
    
    int mid = left + (right - left) / 2;
    
    if (array[mid] == target)
    {
        return mid;  // 基础情况：找到了
    }
    else if (array[mid] < target)
    {
        // 递归调用：在右半部分查找
        return BinarySearchRecursive(array, target, mid + 1, right);
    }
    else
    {
        // 递归调用：在左半部分查找
        return BinarySearchRecursive(array, target, left, mid - 1);
    }
}
​
// 使用递归版本
int result = BinarySearchRecursive(sortedNumbers, target, 0, sortedNumbers.Length - 1);

4. 完整示例：带详细日志

using System;
​
class BinarySearchDetailed
{
    static void Main()
    {
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 };
        int[] targets = { 7, 20, 25, 0 };
        
        foreach (int target in targets)
        {
            Console.WriteLine($"\n{'='.PadRight(40, '=')}");
            Console.WriteLine($"查找目标值: {target}");
            Console.WriteLine($"数组: [{string.Join(", ", numbers)}]");
            
            int result = BinarySearchWithLogging(numbers, target);
            
            if (result != -1)
            {
                Console.WriteLine($"✅ 成功！目标值 {target} 在索引 {result} 位置");
            }
            else
            {
                Console.WriteLine($"❌ 失败！目标值 {target} 不在数组中");
            }
        }
    }
    
    static int BinarySearchWithLogging(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;
        int steps = 0;
        
        while (left <= right)
        {
            steps++;
            int mid = left + (right - left) / 2;
            
            Console.WriteLine($"步骤{steps}: 检查范围 [{left}-{right}]，中间索引 {mid}，值 {array[mid]}");
            
            if (array[mid] == target)
            {
                Console.WriteLine($"  比较: {array[mid]} == {target} ✓");
                Console.WriteLine($"  总共用了 {steps} 步查找");
                return mid;
            }
            else if (array[mid] < target)
            {
                Console.WriteLine($"  比较: {array[mid]} < {target}，向右查找 →");
                left = mid + 1;
            }
            else
            {
                Console.WriteLine($"  比较: {array[mid]} > {target}，向左查找 ←");
                right = mid - 1;
            }
        }
        
        Console.WriteLine($"  查找结束，总共用了 {steps} 步");
        return -1;
    }
}

5. 算法特点分析

优点：

• ✅ 极快：时间复杂度 O(log n)，比顺序查找的 O(n) 快得多

• ✅ 高效：数据量越大，优势越明显

• ✅ 简单：逻辑清晰，容易理解

缺点：

• ❌ 必须有序：要求数据预先排序

• ❌ 内存连续：通常需要数组这样的连续存储结构

• ❌ 不适合动态数据：如果数据频繁变动，维护排序的成本高

6. 时间复杂度对比

惊人的效率差异：在100万个元素中查找，顺序查找最多需要100万次比较，而二分查找最多只需要20次！

7. 重要细节说明

为什么使用 left + (right - left) / 2？

这是为了防止整数溢出。如果使用 (left + right) / 2，当 left 和 right 都很大时，left + right 可能超过 int 的最大值。

// 安全的方式（推荐）
int mid = left + (right - left) / 2;
​
// 有风险的方式（不推荐）
int mid = (left + right) / 2;  // 可能溢出！

边界条件处理

// 检查数组是否为空
if (array == null || array.Length == 0)
{
    return -1;
}
​
// 检查目标值是否在数组范围内（可选优化）
if (target < array[0] || target > array[array.Length - 1])
{
    return -1;  // 肯定不在数组中
}

8. 实际应用练习

练习1：查找第一个大于等于目标的值

// 查找第一个大于或等于目标值的元素位置
static int FindFirstGreaterOrEqual(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;
    int result = -1;
    
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        
        if (array[mid] >= target)
        {
            result = mid;  // 记录候选位置
            right = mid - 1;  // 继续向左找更小的满足条件的位置
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return result;  // 返回第一个满足条件的位置，或-1
}

练习2：使用 C# 内置方法

// C# 提供了内置的二分查找方法
int[] numbers = { 1, 3, 5, 7, 9, 11, 13 };
int index = Array.BinarySearch(numbers, 7);
​
if (index >= 0)
{
    Console.WriteLine($"找到在位置 {index}");
}
else
{
    Console.WriteLine("未找到");
}

9. 常见错误与调试技巧

常见错误：

1. 忘记排序：对无序数组使用二分查找

2. 边界错误：left <= right 写成 left < right

3. 更新错误：left = mid 而不是 left = mid + 1

调试技巧：

// 添加调试输出
Console.WriteLine($"left={left}, right={right}, mid={mid}, array[mid]={array[mid]}");
​
// 或者使用调试器设置断点，观察变量变化

总结

二分查找是必须掌握的重要算法：

• 前提：数据必须有序

• 核心：每次排除一半的搜索范围

• 优势：极其高效，特别适合大型数据集

• 关键：正确处理边界条件和中间值计算

记住：当有人问"这个数据需要排序吗？"，如果要用二分查找，答案就是"必须排序！"

试着运行上面的代码，修改参数来体验二分查找的强大威力吧！