17370845950

Array.BinarySearch是最稳妥的选择，它提供泛型安全、边界完善的二分查找，支持所有一维数组，未找到时返回负数（按位取反为插入位置），需判正负而非直接作索引。

用 Array.BinarySearch 是最稳妥的选择

绝大多数场景下，不需要手写二分查找——C# 运行时已提供高度优化、泛型安全、边界处理完善的 Array.BinarySearch 方法。它支持所有一维数组（int[]、string[]、自定义类型等），且自动处理未找到时的负数返回值（按位取反后为插入位置）。

常见错误是直接把返回值当索引用，忽略负数含义：

int[] arr = { 1, 3, 5, 7, 9 };
int index = Array.BinarySearch(arr, 6); // 返回 -4，不是“没找到就返回 -1”
if (index < 0) {
    Console.WriteLine($"应插入到位置 {~index}"); // 输出：应插入到位置 3
}

手写二分查找时必须检查 left

手动实现最容易出错的是循环条件和边界更新。典型错误写法：while (left 或漏掉 mid 的等于判断，导致漏查或死循环。

标准实现要点：

• 初始 right = arr.Length - 1，不是 arr.Length
• 循环条件严格为 left
• 更新时用 right = mid - 1 和 left = mid + 1，不能写成 = mid
• 每次计算 mid = left + (right - left) / 2 防止整数溢出（尤其在大数组中）

static int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

List.BinarySearch 和 Span.BinarySearch 的适用场景

如果数据来自 List，优先用其 BinarySearch 方法，它内部调用相同逻辑，但避免了数组拷贝开销；若处理的是栈上切片（如从大数组中取一段），Span.BinarySearch 更高效，零分配且支持自定义 IComparer。

注意：二者都要求输入已排序，且不自动验证——传入乱序数据会返回错误结果，不会抛异常。

• List.BinarySearch：适合频繁读、偶有修改的集合
• Span.BinarySearch：适合高性能数值计算、内存敏感场景（.NET Core 2.1+）
• 三者都不支持多维数组，需自行展平或改用其他结构

泛型版本要小心 IComparable 和 null

对引用类型（如 string 或自定义类）使用泛型二分时，若元素可能为 null，而比较器未显式处理，Array.BinarySearch 可能抛 NullReferenceException。

解决方式：

• 用带 IComparer 参数的重载，例如 StringComparer.Ordinal
• 自定义类型确保实现 IComparable 并正确处理 null
• 避免依赖默认比较器处理可空引用类型

比如搜索含 null 的字符串数组：

string[] arr = { "a", nu
ll, "c" };
// ❌ 危险：Array.BinarySearch(arr, "b") 可能崩
// ✅ 安全：指定比较器
int idx = Array.BinarySearch(arr, "b", StringComparer.Ordinal);

实际用的时候，先确认数据是否已排序、是否允许 null、是否需要插入位置信息——这些细节比算法本身更容易导致线上问题。