C++二分查找算法实战指南

C二分查找算法详解二分查找Binary Search是一种在有序数组中查找特定元素的高效算法。其核心思想是通过不断缩小搜索范围将时间复杂度从线性搜索的O(n)降低到O(log n)。以下是手动实现二分查找的完整解析基本二分查找实现基础版本的二分查找适用于无重复元素的有序数组int binarySearch(int arr[], int size, int target) { int left 0; int right size - 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; // 未找到 }关键点说明循环条件left right确保搜索区间有效mid left (right - left)/2的写法比(leftright)/2更安全避免整数溢出每次比较后区间缩小约一半查找左边界版本当数组中有重复元素时可能需要找到目标值的第一个出现位置int leftBound(int arr[], int size, int target) { int left 0; int right size; // 注意右边界 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { right mid; // 收缩右边界 } else { left mid 1; // 收缩左边界 } } // 检查越界和是否找到 if (left size || arr[left] ! target) { return -1; } return left; }特点右边界初始值为size而非size-1循环条件变为left right找到目标后继续向左搜索查找右边界版本类似地可以找到目标值的最后一个出现位置int rightBound(int arr[], int size, int target) { int left 0; int right size; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // 收缩左边界 } else { right mid; // 收缩右边界 } } // 需要返回left-1 if (left 0 || arr[left-1] ! target) { return -1; } return left - 1; }注意事项最终返回的是left-1需要额外检查边界条件浮点数二分查找二分查找也可用于浮点数计算如求平方根double sqrtBinarySearch(double x, double precision) { double left 0, right x; while (right - left precision) { double mid left (right - left) / 2; double square mid * mid; if (square x) { left mid; } else if (square x) { right mid; } else { return mid; } } return left; }特点使用精度控制循环终止适用于连续函数求根问题二分查找变种应用旋转数组查找在部分有序的旋转数组中查找目标int searchRotatedArray(int arr[], int size, int target) { int left 0, right size - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; // 判断哪部分是有序的 if (arr[left] arr[mid]) { // 左半部分有序 if (arr[left] target target arr[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半部分有序 if (arr[mid] target target arr[right]) { left mid 1; } else { right mid - 1; } } } return -1; }查找峰值元素在非严格有序数组中查找局部峰值int findPeakElement(int arr[], int size) { int left 0, right size - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] arr[mid 1]) { left mid 1; } else { right mid; } } return left; }常见错误与调试技巧死循环问题确保每次迭代区间都在缩小检查循环终止条件是否合理边界错误初始化时right应设为size-1还是size返回时是left还是left-1溢出问题使用mid left (right - left)/2而非(leftright)/2测试用例void testBinarySearch() { int arr1[] {1,3,5,7,9}; assert(binarySearch(arr1, 5, 5) 2); assert(binarySearch(arr1, 5, 0) -1); int arr2[] {1,2,2,2,3}; assert(leftBound(arr2, 5, 2) 1); assert(rightBound(arr2, 5, 2) 3); }性能优化建议对于小型数组n100线性搜索可能更快在多次查询时考虑使用哈希表预处理对于特定硬件架构可以尝试循环展开优化扩展应用场景数学问题求解如求方程根资源分配问题如书籍页码分配机器学习中的超参数调优数据库索引优化通过掌握这些实现方法和变种可以解决大多数需要二分查找算法的编程问题。每种变体都有其特定的应用场景理解其背后的原理比记忆代码更重要。