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

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} 处); }8. 常见面试题与应用场景在旋转有序数组中查找目标值LeetCode 33。寻找峰值元素LeetCode 162。计算平方根LeetCode 69。搜索二维矩阵LeetCode 74。在有序数据集合中快速定位、范围查询等。这些题目本质上都是二分查找思想的延伸掌握了基础实现后可以灵活运用边界调整来适应不同需求。9. 总结实现时牢牢记住三点有序数组、正确的中间点计算和合适的边界收缩。平时也可以直接使用Array.BinarySearch减少重复造轮子但理解其背后的原理才能让你在复杂问题中游刃有余。新手强烈推荐看b站up蓝不过海的演示视频