当前位置：首页 > news >正文

C# 二分查找：从原理到实现(新学者思考)

news 2026/7/23 4:16:56

1. 什么是二分查找

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想是“分而治之”：每次将搜索范围缩小一半，直到找到目标值或范围为空。时间复杂度为 O(log n)，比线性查找的 O(n) 快得多，尤其适合大规模数据。

2. 算法原理

二分查找的基本步骤如下：

设定左右边界 left 和 right，初始分别为数组的第一个和最后一个索引。
计算中间索引 mid = left + (right - left) / 2，这样可以防止大数相加时溢出。
将中间元素与目标值比较：
- 若相等，返回 mid；
- 若中间元素小于目标值，说明目标在右半部分，将 left 更新为 mid + 1；
- 若中间元素大于目标值，说明目标在左半部分，将 right 更新为 mid - 1。
重复步骤 2-3，直到 left 大于 right，表示未找到目标值。

3. 边界条件与常见坑点

在实际编码中，二分查找的边界处理非常容易出错，重点关注：

循环条件：使用 while (left <= right)，当 left 和 right 相等时仍需判断该位置。
中间索引计算：优先使用 left + (right - left) / 2，避免 (left + right) / 2 的溢出风险。
左右边界更新：left = mid + 1 或 right = mid - 1，否则可能陷入死循环。
返回值：未找到时通常返回 -1 或插入位置的按位取反值。

4. C# 标准实现（迭代版）

下面给出一个经典的迭代二分查找方法，适用于 int 数组：

/// <summary> /// 在有序整数数组中执行二分查找，返回目标值的索引，未找到返回 -1。 /// </summary> public static int BinarySearch(int[] arr, int target) { if (arr == null || arr.Length == 0) return -1; int left = 0; int right = arr.Length - 1; while (left <= right) { // 安全计算中间索引，避免溢出 int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; // 目标在右半区 } else { right = mid - 1; // 目标在左半区 } } return -1; // 未找到 }

5. C# 递归实现

二分查找也可以写成递归形式，逻辑更直观，但需要注意递归深度和栈空间消耗：

/// <summary> /// 二分查找的递归版本，返回目标索引，未找到返回 -1。 /// </summary> public static int BinarySearchRecursive(int[] arr, int target) { return BinarySearchRecursive(arr, target, 0, arr.Length - 1); } private 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; else if (arr[mid] < target) return BinarySearchRecursive(arr, target, mid + 1, right); else return BinarySearchRecursive(arr, target, left, mid - 1); }

6. 查找第一个或最后一个目标值（变种）

如果数组中有重复元素，可能需要找到第一次出现的位置或最后一次出现的位置。这是二分查找的常见变种，在 C# 中也很容易实现：

/// <summary> /// 查找目标值在数组中第一次出现的索引。 /// </summary> public static int FindFirst(int[] arr, int target) { int left = 0, right = arr.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; // 记录当前找到的位置 right = mid - 1; // 继续向左搜索更早的匹配 } else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return result; } /// <summary> /// 查找目标值在数组中最后一次出现的索引。 /// </summary> public static int FindLast(int[] arr, int target) { int left = 0, right = arr.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; // 记录当前找到的位置 left = mid + 1; // 继续向右搜索更晚的匹配 } else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return result; }

7. 使用 C# 内置的 Array.BinarySearch

.NET 框架本身就提供了二分查找方法Array.BinarySearch，它返回的是找到的索引；如果未找到，则返回一个负数，其按位取反后就是目标应插入的位置。使用起来非常方便：

int[] sortedArray = { 1, 3, 5, 7, 9 }; int index = Array.BinarySearch(sortedArray, 5); // 返回 2 int notFound = Array.BinarySearch(sortedArray, 4); // 返回负数 if (notFound < 0) { // ~notFound 就是 4 应该插入的位置，以保持数组有序 int insertPos = ~notFound; Console.WriteLine($"4 应插入在索引 {insertPos} 处"); }