扶鞘引狂澜剑意万重开。欢迎来到丘山望岳的小栈今天学习的内容是二分算法我们闲言少叙直击主题。一、核心概念引入——二段性二段性就是指一个数组呈现一定规律排布如果拿出一个元素查看信息就可以知道其左边元素具有性质A,右边的元素具有性质B且不存在具有性质AB的元素。比如有一个升序数组【123456789】随便取出一个元素就可以发现其左边的任意元素都比这个元素要小性质A)右边的任意元素都比这个元素要大(性质B且在数组中不存在一个元素既拥有性质A也拥有性质B即这个数组具有二段性。二段性的作用我们已知一个元素在具有二段性的数组当中时根据观察数组的规律二段性结合待查找元素的性质就可以在不断缩小搜索范围中忽略一些区间的查找实现时间复杂度小于o(1)的查找方式。经典母题题目来源leetcode 704.⼆分查找给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。示例 1:输入:nums [-1,0,3,5,9,12],target 9输出:4解释:9 出现在nums中并且下标为 4示例 2:输入:nums [-1,0,3,5,9,12],target 2输出:-1解释:2 不存在nums中因此返回 -1题目分析数组【12345678910】查找9这个数组具有二段性随便挑出一个元素左边的元素比这个元素小右边的元素比这个元素大1.如果这个元素比待查找的值小证明了待查找的值一定不在选出元素的右边即选出元素右边部分到数组末尾的元素可忽略。下次在保留元素的数组中继续查找。2.如果这个元素比待查找的值大证明了待查找的值一定不在选出元素的左边即数组开头到选出元素左边的部分的元素可忽略。下次在保留元素的数组中继续查找。3.如果这个元素就是待查找的元素返回其下标。每次查找挑选的这个元素的方法也有讲解经过严格的数学证明每次查找挑选数组中间位置的元素可以使得代码效率最高。这就是二分算法的基础思想。简单演示一下代码的运行第一次 挑出5 ,59 锁定新查找区间【12345678910】第二次 挑出889锁定新查找区间【12345678910】第三次 挑出999返回下标8找到了数值为9的元素代码实现class Solution { public: int search(vectorint nums, int target) { int left0; int rightnums.size()-1; while(leftright) { int mid(leftright)/2; if(nums[mid]target)return mid; else if(nums[mid]target)leftmid1; else rightmid-1; } return -1; } };值得一提的是这里的取中间元素的算法有两种第一种mid1left(right-left)/2;第二种mid1left(right-left1)/2;这样写可以有效的避免数据的溢出。思想也很好理解在left的基础之上加上right和left的差值的一半。区别就在于当数组元素个数是奇数时如【12345】mid1mid22,即3所在位置的下标。当数组元素个数是偶数时如【1234】mid11,即2所在位置的下标mid22即3所在位置的下标;所以mid1是向下取整的mid2是向上取整的这个算法在一些有特定取整条件返回值的题中也会用到。二分的时间复杂度计算我们可以得到如果一个数组有n给元素通过t次找到了指定元素由于每次查找都在上一次的基础之上忽略了一半的元素第1次查找后还剩n/2个元素第2次查找时还剩n/2^2个元素…………第t次查找时还剩n/2^t个元素1总结规律2^tn 即tlog n;时间复杂度为O(logn)朴素二分的模板总结这里总结一下朴素二分的算法模板left左端right右端 while(leftright)//leftright也行 { mid1left(right-left)/2;//mid1left(right-left1)/2;也行 if(条件1 leftmid1;//...... else if(条件2rightmid-1;//...... else //...... }当然朴素二分应用场景是很局限的常用的是下面两个场景中的二分模板我们通过一道例题讲解Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [5,7,7,8,8,10] , target 8输出[3,4]示例 2输入nums [5,7,7,8,8,10] , target 6输出[-1,-1]示例 3输入nums [], target 0输出[-1,-1]先给出题解class Solution { public: vectorint searchRange(vectorint nums, int t) { vectorint ret(2,-1); //处理越界特殊情况 if(nums.size()0)return ret; //找左端点 int left0,rightnums.size()-1; for(;leftright;) { int midleft(right-left)/2; if(nums[mid]t)leftmid1; else rightmid; } if(nums[left]t)ret[0]left; //找右端点 left0,rightnums.size()-1; for(;leftright;) { int midleft(right-left1)/2; if(nums[mid]t)leftmid; else rightmid-1; } if(nums[right]t)ret[1]right; return ret; } };下面要讲的两个二分算法和朴素二分算法的根本区别就是朴素二分算法有三个分支在待查找元素是不符合性质A且不符合性质B的下面两个二分中循环中只有两个分支就待查找元素符合性质A还是性质B做出划分。首先说两个细节问题这两个细节决定了二分算法的成败1.while循环中循环条件是leftright还是leftright2.中间点下标的算法是mid1left(right-left)/2还是mid1left(right-left1)/2。一般来说while的条件是第一个而中间值下标算法要根据下面讲的两个模板来视题目情况而定。继续题目讲解就【12344478】为例子二、查找区间左端点的二分1.发现二段性由于左端点左边的值都比给的值要小本身和右边的值都比给的值要大或相等。我们通过改良朴素二分算法实现1.通过取中算法判断中间值是否比给定的值要小如果是舍弃mid左边的所有元素和自身在leftmid1到原来的right这个区间继续查找2.反之舍弃mid右边的元素但不能舍弃midmid为左端点也有可能触发分支条件在left到rightmid这个区间继续查找。接下来就要解决细节问题1.我们根据普遍的代码习惯while循环条件选择leftright这样当leftright时跳出循环left或right就是指定查找的左端点元素位置的下标。2.直接说结论选择mid1left(right-left)/2如果选择mid1left(right-left1)/2在最后一轮查找只有两个元素时【99】mid21,触发分支2right1,left0,出现死循环。代码运行过程查找左边界第一个出现 4 的位置初始状态left0right7数组长度 8下标 0~7循环条件left right第 1 轮循环(mid 0 (7-0)/2 3)(nums[3]4\)不满足(nums[mid]4)执行rightmid3此时left0right3(03)继续循环第 2 轮循环(mid 0 (3-0)/2 1)(nums[1]2 4)执行leftmid12此时left2right3(23)继续循环第 3 轮循环(mid 2 (3-2)/2 2)(nums[2]3 4)执行leftmid13此时left3right3不满足leftright循环退出左边界判定(nums[3]4 target)因此左边界ret[0]3模板int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; // 向下取整 mid if (nums[mid] t) { left mid 1; // mid 太小左边界右移 //...... } else { right mid; // mid t答案在左侧含mid收缩右边界 //...... } }三、查找区间右端点的二分1.发现二段性由于右端点左边和本身的值都比给的值要小或相等右边的值都比给的值要大。我们通过改良朴素二分算法实现1.通过取中算法判断中间值是否比给定的值要大如果是舍弃mid右边的所有元素和自身在left到rightmid-1这个区间继续查找2.反之舍弃mid左的元素但不能舍弃midmid为右端点也有可能触发分支条件在leftmid到right这个区间继续查找。接下来就要解决细节问题1.我们根据普遍的代码习惯while循环条件选择leftright这样当leftright时跳出循环left或right就是指定查找的右端点元素位置的下标。2.直接说结论选择mid1left(right-left1)/2如果选择mid1left(right-left)/2在最后一轮查找只有两个元素时【99】mid10,触发分支2right1,left0,出现死循环。代码运行过程查找右边界最后一个出现 4 的位置重置初始状态left0right7循环条件left rightmid 计算式改为(midleft(right-left1)/2)第 1 轮循环(mid 0 (7-01)/2 4)(nums[4]4)执行leftmid4此时left4right7(47)继续循环第 2 轮循环(mid 4 (7-41)/2 6)(nums[6]7 4)执行rightmid-15此时left4right5(45)继续循环第 3 轮循环(mid 4 (5-41)/2 5)(nums[5]4 )执行leftmid5此时left5right5不满足leftright循环退出右边界判定(nums[5]4 target)因此右边界ret[1]5模板int left 0, right nums.size() - 1; while (left right) { int mid left (right - left 1) / 2; // 向上取整 mid if (nums[mid] t) { left mid; // mid t答案在右侧含mid收缩左边界 //…… } else { right mid - 1; // mid 太大右边界左移 //…… } }练习二分的整个模板和理论知识到这里就结束了我们来几个题目来强化一下69. x 的平方根https://leetcode.cn/problems/sqrtx/模板的选用特此声明选择二分模板中查找区间左端点的模板还是右端点的模板要视情况而定有些题目二者兼顾但是这道题目只能使用查找区间右端点的模板。二段性返回值属性x的平方根所以假设建立一个整数的平方的数组这里不对数组元素经行运算可以简化如下待查找的左边的值即自身都是比自身小或等右边的值都是比自身大无脑套用查找区间右端点的模板class Solution { public: int mySqrt(int x) { long long left0,rightx; while(leftright) { long long midleft(right-left1)/2; long long temp mid*mid; if(temp(long long)x) rightmid-1; else leftmid; } return left; } };结论也就是说一切关于模板的选用要根据待查找元素得出数组二段性从而通过类比法类比模板中的二段性来决定。852. 山脉数组的峰顶索引https://leetcode.cn/problems/peak-index-in-a-mountain-array/数组二段性由数学中定义arr[i])-(arr[i1])0数组元素单调增左-右0数组元素单调减指定待查找位置左边都是单调增的右边即自身是单调减的类比二段性套用查找区间左端点的模板。题解class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left0,rightarr.size()-1; while(leftright) { int midleft(right-left)/2; if(arr[mid]arr[mid1]) leftmid1; else rightmid; } return right; } };最后以一道两个模板都可以使用的题目压轴153. 寻找旋转排序数组中的最小值https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/题解一二段性分析取最后一个元素为基准由这个左旋的性质待查找位置即自身之后的值都比这个基准要小或相等左边的元素的值都比这个基准要大无脑套用查找区间左端点的模板class Solution { public: int findMin(vectorint nums) { int tnums[nums.size()-1]; int left0,rightnums.size()-1; while(leftright) { int midleft(right-left)/2; if(nums[mid]t)rightmid; else leftmid1; } return nums[left]; } };题解二二段性分析取数组中首元素为基准待查找元素前一个元素左边即自身的值比之小或相等右边即自身的值比之大套用查找区间右端点的模板class Solution { public: int findMin(vectorint nums) { int left0,rightnums.size()-1; int tnums[0]; while(leftright) { int midleft(right-left1)/2; if(nums[mid]t)leftmid; else rightmid-1; } return rightnums.size()-1?nums[0]:nums[right1]; } };本期内容分享结束感谢各位观众老爷的支持完结撒花