目录1、算法原理2、时间复杂度2、标准二分查找模板3、常用二分查找模板4、利用二分查找求数的立方根1、算法原理在序列中查找目标值target时若序列具有二段性特征即能被划分为两个满足不同性质的子序列则可以通过判断中间值所属的性质直接排除其中一半的序列元素。再判断没有被排除的序列中间值所属的性质再直接排除其中一半的序列元素直到只剩下一个序列元素则这个序列元素可能是目标值。2、时间复杂度每次都排除一半的序列元素直到只剩下一个序列元素。假设序列有 n 个元素每次判断后剩下的元素个数n/2 ---- n/(2^2) ---- n/(2^3) ---- n/(2^4) ---- n/(2^5) ---- n/(2^6) ---- ... ---- n/(2^N) 1则 N lognN 就是查找的次数所以时间复杂度是O(logn)求序列的中间值索引的方式1、mid left (right - left) / 2;2、mid left (right - left 1) / 2;这两种方式在标准二分查找模板都可以但在常用二分查找模板有区别。不推荐 mid (left right) / 2这种方式如果序列太长容易溢出。2、标准二分查找模板在一段序列中查找目标值int left 0,right nums.size() - 1; while(left right) // 注意循环继续的条件 { int mid left (right - left) / 2; // 如果序列太长防止溢出 if(...) right mid - 1; else if(...) left mid 1; else return ...; } return ...; // 说明... 是根据题目所推导的二段性例题class Solution { public: int search(vectorint nums, int target) { int left 0,right nums.size() - 1; while(left right) { int mid left (right - left) / 2; if(nums[mid] target) right mid - 1; else if(nums[mid] target) left mid 1; else return mid; } return -1; } };3、常用二分查找模板将序列分为左右两个序列左右两个序列的元素都满足某个特点而要查找的元素通常是左序列的右端点或者是右序列的左端点。如果要查找的目标值是右序列的左端点while (left right) { int mid left (right - left) / 2 if (mid 所指向的元素满足右序列的特点) right mid; else if (mid 所指向的元素满足左序列的特点) left mid 1; }注意1、注意求序列中间值的方式不能写成 int mid left (right - left 1) / 2; 否则会死循环2、不能是 right mid - 1; 因为 mid 所在位置可能就是目标值如果要查找的目标值是左序列的右端点while (left right) { int mid left (right - left 1) / 2 if (mid 所指向的元素满足右序列的特点) right mid - 1; else if (mid 所指向的元素满足右序列的特点) left mid; }注意1、注意求序列中间值的方式不能写成 int mid left (right - left) / 2; 否则会死循环2、不能是 left mid - 1; 因为 mid 所在位置可能就是目标值记忆技巧如果在更新 left 和 right 时如果出现 -1那么更新 mid 就要 1例题二段性分析以求左端点为例这道题的二段性可以是将序列分为两个子序列左序列都是小于 target 的值而右序列都是大于等于 target 的值查找的目标是右序列的左端点即 target 第一次出现的位置。class Solution { public: vectorint searchRange(vectorint nums, int target) { vectorint ret {-1,-1}; int left 0; int right nums.size() - 1; if(nums.size() 0) return ret; //处理边界情况 // 寻找左端点 while(left right) { int mid left (right - left) / 2; if(nums[mid] target) left mid 1; if(nums[mid] target) right mid; } if(nums[left] target) ret[0] left; else return ret; // 寻找右端点 left 0; right nums.size() - 1; while(left right) { int mid left (right - left 1) / 2; if(nums[mid] target) left mid; if(nums[mid] target) right mid - 1; } if(nums[right] target) ret[1] right; else return ret; return ret; } };二段性分析这道题的二段性可以是左序列都是平方后小于等于 target 的值而右序列都是平方后大于 target 的值。class Solution { public: int mySqrt(int x) { int left 0,right x; long long mid 0; // 防止溢出 while(left right) { mid left (right - left 1) / 2; if(mid * mid x) right mid - 1; else if(mid * mid x) left mid; else if(mid * mid x) return mid; } return left; } };二段性分析这道题的二段性可以是将序列分为两个子序列左序列都是小于 target 的值而右序列都是大于等于 target 的值。最后 left 和 right 相遇指向的值时有两种情况1、该值大于等于 target此时直接返回 left 或 right2、该值小于 target因为序列的值可能都是小于 target 的值此时返回 left 1 或 right 1。int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) right mid; else if (nums[mid] target) left mid 1; } if (nums[left] target) return left 1; else return left;二段性分析数组可以分为左右两个子序列左序列是包含峰顶在内的递增序列右序列是递减序列。左序列元素的特点是从下标为 1 的元素开始每个元素都大于它前一个元素右序列元素的特点是每个元素都小于它前一个元素。class Solution { public: int peakIndexInMountainArray(vectorint arr) { // 数组首元素和最后一个元素不可能是峰顶 int left 1,right arr.size() - 2; while(left right) { int mid left (right - left 1) / 2; if(arr[mid] arr[mid - 1]) left mid; else right mid - 1; } return left; } };二段性分析关键是某一时刻选取到的 mid 指向的元素通过该元素与它下一个元素做比较如果 mid 大于它下一个元素那么峰值可能是 mid 或可能是包含在 mid 左边的某个元素如果 mid 小于它下一个元素那么峰值可能是包含在 mid 右边的某个元素。class Solution { public: int findPeakElement(vectorint nums) { int left 0,right nums.size() - 1; while(left right) { int mid left (right - left) / 2; if(nums[mid] nums[mid 1]) right mid; else if(nums[mid] nums[mid 1]) left mid 1; } return left; } };二段性分析根据题目由于序列的元素互不相同我们把序列抽象成折线图如果 mid 落在 AB 段那么 mid指向的元素一定大于 D 点序列最后一个元素此时应该到右序列寻找left mid 1如果 mid 落在 CD 段那么 mid 指向的元素一定小于等于 D 点此时应该到序列左端点寻找right midmid 可能落在 C 点所以不能是 right mid - 1。class Solution { public: int findMin(vectorint nums) { int left 0,right nums.size() - 1; int flag nums[right]; while(left right) { int mid left (right - left) / 2; if(nums[mid] flag) left mid 1; else right mid; } return nums[left]; } };这道题可以一题多解1、哈希表 2、暴力解法 3、位运算 4、求和公式 5、二分查找。二段性分析在缺失某个数字之前的数字该数字与它的下标一一对应缺失的哪个数字及以后下标不对应。根据该性质可以将序列分为两个子序列下标对应的序列与下标不对应的序列。class Solution { public: int takeAttendance(vectorint records) { int left 0,right records.size() - 1; while(left right) { int mid left (right - left) / 2; if(mid records[mid]) left mid 1; else right mid; } if(left records[left]) return left 1; else return left; } };4、利用二分查找求数的立方根double cubeRootBinarySearch(double x, double precision 1e-7) { // 第1步处理特殊情况 // 0的立方根是0直接返回 if (x 0) return 0; // 第2步处理负数 // 记录原始数字是否为负数 bool isNegative x 0; // 对负数取绝对值方便计算 x fabs(x); // 第3步确定初始搜索范围 double left, right; // 立方根的特性分析 // - 如果 x ≥ 1则立方根 ≤ x例如8的立方根2 ≤ 8 // - 如果 0 x 1则立方根 x例如0.125的立方根0.5 0.125 if (x 1) { left 0; // 最小值从0开始 right x; // 最大值不会超过x本身 } else { left x; // 对于小于1的数立方根大于它本身 right 1; // 但不会超过1 } // 第4步二分查找主循环 double mid; // 循环条件当区间长度大于精度要求时继续 // precision 1e-7 保证了最终结果至少有6位小数精度 while (right - left precision) { // 计算区间中点 mid (left right) / 2; // 计算中点的立方值 double cube mid * mid * mid; // 第5步比较并调整搜索区间 if (cube x) { // 如果 mid³ x说明 mid 太大 // 真正的立方根在左半区间 [left, mid] right mid; } else { // 如果 mid³ ≤ x说明 mid 可能太小或是正确答案 // 真正的立方根在右半区间 [mid, right] left mid; } // 注意这里不需要处理 cube x 的特殊情况 // 因为浮点数相等很难精确判断交给精度控制 } // 第6步返回结果 // 循环结束时left 和 right 非常接近 // 取它们的平均值作为最终结果 double result (left right) / 2; // 如果是负数返回负值 return isNegative ? -result : result; }5、二分答案P3853 [TJOI2007] 路标设置 - 洛谷二段性分析要使“空旷指数”越小我新设置的路标的数量应该越小反之越大