2962. 统计最大元素出现至少 K 次的子数组
题目链接：https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/我的思路想到用滑动窗口双指针，但是在结果计算和指针移动的判断上还是有些不太对，思路是清晰的，离正确答案之差一点点。首先求出$nums$中的最大值记为$m$，初始化左指针$l=0$，定义一个变量$cnt$统计枚举过程中最大值出现了几次，接着用enumerator枚举$r,x$，如果$x=m$，则将$cnt+1$，当$cnt\geq k$时，进入while循环判断，此时意味着到了某个符合条件子数组的边界，$ans+1$，如果$nums[l]=m$，则将$cnt-1$，同时将左指针右移$l+1$，因为我们要统计的是子数组的个数，所以在考察完每个$r,x$时，再将左指针重置，$l=0$，以免漏掉情况，如此循环判断下去，返回$ans$分析这个思路看上去很正确，但存在考察不全的情况，尽管想到了重置左指针，但由于$cnt$的值动态变化，所以会漏掉计数。比如案例$[1,3,2,3,3], k = 2$，按照上面的思路，将每一步计算的$cnt$值和子数组打印出来得到：2 [1, 3, 2, 3]2 [3, 2, 3]2 [1, 3, 2, 3, 3]2 [3, 2, 3, 3]到这里程序就退出运行了，原因出在考察到第三个3时。在$r=3$时，对应的$nums[3]=3$为第二个3，此时$cnt=2$，满足while循环进入条件，接着开始计数，做指针开始右移，得到一开始的两个结果（前两行），但由于$l$移动到1时，$nums[1]$也是3，因此$cnt-1$，$cnt$变为1，跳出循环，$l$重置为0，继续考察数组元素，$r=4,x=3$，$cnt$再加1，得到$cnt=2$，满足while进入条件，开始计数，得到后面两行的结果，但同样的，当$l$再次移动到1时，$nums[1]=3$，使得$cnt-1$，变成1，不再符合while的条件，便跳出循环了，得到错误的结果。纠正滑动窗口问题中，应该不走回头路，试想当$r=3$时，左指针开始移动，滑动到$l=1$时碰到最大值，那么说明$nums[1]$的这个3不能再用了（不要回头，不然会很复杂），我们要将这种情况下的所有可能全部计算出来，接着考虑后面的元素，每一个元素都如此，便能计算到最准确的结果回到上面那个情况，$r=3,x=3$，进入while判断，$l$到1后$cnt-1$，$l$再加1后跳出循环（因为$l+1$是写在while中的最后一句），此时$l$变为2，那么此时对应的，在右边界为$r=3$的情况下，符合条件的数组数不就是2个吗？因此只需要$ans+l$即可，非常巧妙换句话说，其实我们只要找到每个“临界”情况，再将此时的$l$累加起来，就是最后的答案。再看$r=4$的情况，上一个循环中$l$被赋值为2，那么同样地，$l$会以4跳出while循环，此时对应的符合条件的数组不就是4个嘛，分别是$[1,3,2,3,3],[3,2,3,3],[2,3,3],[3,3]$，因为有最后一个元素的加进来，所以不会考察到与之前重复的情况，最后将4和2相加，6就是最终的答案反思双指针/滑动窗口问题中，一般不会将左指针进行重置，一方面容易考察重复情况产生错误，另一方面思路会不够清晰，容易搞混这题还有一个优化的点是，可以直接利用$k$，节省内存占用，遇到最大值就将其减1，while的循环进入条件为$k=0$，当左指针滑到最大值时，再将$k+1$即可，这样可以节约一些内存其实做题也是一个编码-解码的过程，我们的大脑中存在着latent空间，需要将题目进行解码，知道它是什么意思，同时也要将答案进行编码，二者要在latent上匹配，本质上讲的都是一个东西，二者在高维空间中应该有相似的表示，这样才是最佳的解答结果时间复杂度：$O(N)$空间复杂度：$O(1)$已是最优解
题目链接：https://leetcode.cn/problems/valid-triangle-number/description/我的思路这题是很典型的初中数学题，根据三条边的大小来判断是否能组成一个三角形，想到判断条件为：两边之和大于第三边，两边之差小于第三边。很容易想到暴力枚举法，但这样的效率很低，因此联想到用双指针法，但也没有做进一步的思考，就直接开始动手了纠正首先将nums排序，从中取出已经排好序的三个数$a\leq b\leq c$，那么根据判断条件，要让这三条边能构成一个三角形，有：$a+b>c,a+c>b,b+c>a$，因为已经排好序了，那么后面两个条件必然成立，因此我们的目标转换为判断$a+b$是否大于$c$这里有一个很容易困惑的点，就是第二个条件“两边之差小于第三边”是否能满足？根据上面的讨论，$a+c>b$和$b+c>a$是必然成立的，那么根据这两个式子可以推出：$|b-a|=a-b<c,|b-c|=c-b<a,|a-c|=c-a<b$也必然成立（分别将两个变量移到不等号右边），那么第二个条件天然地满足了，只剩下要判断两个短边的和是否大于长边因此我们可以固定长边，取$c=\mathrm {nums}[i],\forall i\in [2, n-1]$，接着在$[0,i-1]$中进行双指针判断，初始化$l=0,r=i-1$，如果$\mathrm{nums}[l]+\mathrm{nums}[r]>\mathrm {nums}[i]$，就说明从$l$到$r$之间的每个数都满足这个条件，能够构成三角形（因为已经事先排好序），就可以让$ans$加上$r-l$优化这题还有一个更巧妙的操作，但理解起来比较困难，就是用卷积+快速傅里叶变换，numpy包包含了快速傅里叶算法，能有效降低时间复杂度（因为这道题中数组中数字范围小于1000，比较小，因此这个方案可行）。计算不符合条件的情况数（两边之和小于第三边），然后再用一共有几种情况$C_{nums.size}^3$减掉不合理的情况数，就能够得到最终答案，为什么要这样做，通过下面的讨论可以找到答案这里用到了两个关键定理：卷积定理：频域相乘等价于时域卷积，时域卷积等价于频域相乘，即$\mathcal{F}\{f*g\}=\mathcal{F}\{f\}\cdot\mathcal{F}\{g\},\mathcal{F}\{f\cdot g\}=\mathcal{F}\{f\}*\mathcal{F}\{g\}$时域卷积的定义：$(f∗g)[k]=\sum_i​f[i]⋅g[k−i]$，对于每一个可能的和$k$，把所有能组成$i+j=k$的组合的乘积$f[i]g[j]$累加，换句话说可以写成：$(f*f)[s]=\sum_{x+y=s}f[x]f[y]$，表示两数相加和为$s$的组合次数首先构建频率数组，$cnt[x]$表示$x$在所给数组中的出现频次，接着结合快速傅里叶变换做自卷积，得到$cnt2[s]$，表示两边之和为$s$的组合数（可能有几种情况）。参照上面的类似思路，我们固定$cnt$，取其中的元素所对应的边长作为最长边来考虑（考虑的背景是，根据三角形组成判断条件，对每个三元组，最大边必须小于另外两边之和），那么我只需要考察$cnt2[:cnt.size]$这部分的元素，后面的部分没有合理的最长边来与之对应了，因此不在考虑范围内需要注意的是，卷积过程中会出现两种情况：（1）自己加自己；（2）顺序调换相加得到相同结果，这两种情况都会算入到计数中，如下表所示：因此我们需要对$cnt2$中的值进行修正，考虑上面说到的两种情况：自己加自己，相当于把自己*2，因此得到的数一定为偶数，这种情况只会出现在$cnt2$的偶数索引处，因此只需要将$cnt2$偶数位置处的值减掉原来的值$cnt$即可（比如这里$cnt[4]=2$，意味着原来数组中有2个4，$cnt2[8]$中会包含2个自相加的结果，在这道题中我们不能重复利用元素，因此需要减掉2），写成表达式就是：$cnt2[::2]=cnt2[::2]-cnt[:]$，但因为我们上一步中对$cnt2$进行了截取，只取了$cnt.size$这一部分，在取偶数索引部分时，其实只对应了$cnt$的$(cnt.size+1)//2$部分，因此在代码实现时，需要写成$cnt2[::2]-=cnt[:(cnt.size+1)//2]$（以上表为例，$cnt2$被截取$[0:4]$这部分，取偶数索引，对应0,2,4，只有三个元素，这几个元素才会包含自相加的情况，我们为了修正，需要减掉其对应原始数组中元素的出现频次，即0,1,2这三个元素的频次，而在$cnt$中，这三个元素对应前$5+1//2=3$个元素，因此需要这么计算）顺序调换得到相同结果，这种情况比较好处理，在完成第一种情况的处理后，再将$cnt2$整体整除2即可，就能得到修正值这样一来，我们便得到了截取和修正后的$cnt2$数组，接着固定长边进行不合理情况的计算。对于$cnt[i]$，$\mathrm{sum}(cnt2[:i])$表示了两边和小于等于$cnt[i]$的情况总数，我们可以用一个$\mathrm{cumsum}$函数来计算累计求和，实现上面的步骤，得到$pre2=\mathrm{cumsum}(cnt2)$，若某个边长在数组中出现多次，其不合理情况也应按出现次数重复计算，因此还需要将$pre2*cnt$，得到每个长边所对应的不合理的情况总数，最后我们将视角放回到全局，计算出总的不合理情况数$\mathrm{sum}(pre2*cnt)$，再用$C_{nums.size}^3$减掉这个数，即可得到最终结果$C_{nums.size}^3-\mathrm{sum}(pre2*cnt)$反思在FFT法中：因为我们算出的$cnt$是“计数数组”，表示每个元素的出现频次，因此其长度天然地等于$\max (nums)+1$，其末尾元素对应的索引就表示了原始数组中的最大值，通过自卷积操作，算出了任意两边和的情况计数数组$cnt2$，对应的长度天然地等于$2*cnt.size+1$，其末尾元素对应了原始数组中的最大值*2对于这类题我们要找到一个固定约束，比如这道题中固定最长边，再考虑其他边的情况，这样才能不失一般性，不然会很容易重复计算/漏掉情况结果时间复杂度：$O(N+m\log m), m=\max(nums)$空间复杂度：$O(N)$已是最优解
题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/我的思路这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。题解官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这两个问题：如何划分子集令两个序列分别为A, B，那么假设我们在序列A的i索引处切一刀，B的j索引处切一刀，那么我们就可以得到下面的切分：$A[0]\cdots A[i-1]\ |\ A[i]\cdots A[m-1]$$B[0]\cdots B[j-1]\ |\ B[j]\cdots B[m-1]$A中有m个元素，所以一共有m + 1种切分办法，对应地B能有n + 1种切分办法我们把$A[0]\cdots A[i-1]$和$B[0]\cdots B[i-1]$放到一起，称为left_part，剩下的$A[i]\cdots A[m-1]$和$B[j]\cdots B[n-1]$放到一起，称为right_part如何判断切分得合理根据统计中中位数的定义，如果我们的划分合理，那么应该满足：$\max(left\_part)\leq \min(right\_part)$$len(left\_part)=len(right\_part)\ or \ len(right\_part)+1$其中第一条是无论m + n是奇数还是偶数都共同满足的，第二条要分情况，当m + n为偶数时，则取前一个条件，反之取后一个条件，只有这样，才是“恰好”切分，长度上符合要求，数值上也符合要求（不然比如[1,2,3,4|10]和[1,2|9,11]，这样也能满足第一条条件，但并不是最佳的切分，因此还要加上第二条条件）现在我们已经归纳出了两个必要的条件，那么代码实际操作起来该怎么写呢？代码离不开数学表示，有了文字的概念表述，还需要将这些表述进一步转化为数学表达式，才能清晰地在代码中体现和实现算法。根据上面的描述，我们可以得出：$i+j=m-i+n-j$ 或 $i+j=m-i+n-j+1$上述两式分别对应m + n为偶数和奇数时，也就是上面第二点中的第二个条件，对这个式子进行简化，把i + j全部移到一边，可以得到：$i+j=\lfloor\frac{m+n+1}{2}\rfloor$通过向下取整操作，可以将两个式子用上式直观地表达出来，无论m + n是奇数还是偶数，直接代入计算即可。为不失一般性，我们先假设m ≤ n，也就是A的长度小于等于B的长度，于是乎i的取值范围满足$0≤i≤m$（为什么是到m，因为根据第1点的讨论，对于m长的序列而言，有m + 1种划分方法，这里我们不再是二分索引位置，因此范围不是从0到m - 1），那么我们只需要在这个范围内枚举i，即可求得$j=\lfloor\frac{m+n+1}2\rfloor-i$，不需要再加入额外的判断条件了。这种情况下，如果A的长度更长，则只需要交换A和B就行了。但是这种情况下（也是二分法中常见到的特殊情况，就是边界值），i和j有可能触碰到边界值m和n或0，直接获取A[m]会out of index，或A[i-1]即A[-1]会取错值，不符合我们的算法要求，因此需要对这几种情况来进行处理。实际上i和j只代表了划分点的位置，但是在程序里我们要依靠i和j的实际值来取出序列种对应位置的元素值进行判断，比如假设i = 0，那么A的划分点为0，此时A[-1]是不存在的，因为整个序列A都被划进了right_part里，但是根据我们上面的假设，我们又要取A[-1]来作为我们判断left_part里最大值的依据，就会出现错误。处理这种情况的办法其实也很简单，只需要规定：$A[-1]=B[-1]=-\infty, A[m]=B[n]=\infty$即可，理解起来也很简单：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。于是乎，上面的整个讨论过程可以抽象为：在$[0,m]$中找到最大的i，使得$A[i-1]\leq B[j]$，其中$j=\lfloor\frac{m+n+1}2\rfloor-i$那么我们就可以在[0,m]中对i进行二分搜索，找到最大的满足以上条件的i值即可。回顾一下我们的切分思路：$A[0]\cdots A[i-1]\ |\ A[i]\cdots A[m-1]$$B[0]\cdots B[j-1]\ |\ B[j]\cdots B[m-1]$关键的值就在于i - 1, i, j - 1, j这几个位置，这里我们定义几个中间变量来便于比较：nums_i1 = (-inf if i == 0 else nums1[i - 1])nums_i = (inf if i == m else nums1[i])nums_j1 = (-inf if j == 0 else nums2[j - 1])nums_j = (inf if j == n else nums2[j])关键在于比较A[i-1]和B[j]的值，如果满足$A[i-1]\leq B[j]$，那就先赋值一个left_part的最大值median1 = max(nums1[i-1], nums2[j-1]，以及right_part的最小值median2 = min(nums1[i], nums2[j])，这两个中间值用于返回最后的中位数，然后再把搜索区间从左缩小，l = i + 1，看一看i的后面是否还有满足条件的取值，不断缩小区间；如果$A[i-1]>B[j]$，那就说明此时i掠过了我们要找的值，i太靠右了，要从右边缩短区间，r = i - 1，重复以上过程，直到l > r时溢出，返回我们的最终值，如果(m + n) % 2 == 0，说明总长度为偶数，返回两个median值的平方，如果总长度为奇数则返回median1，因为根据我们的算法设计，median1始终是在总长为奇数情况下更长的那一个反思明确二分的对象，是要二分角标、位置，还是要二分元素，充分理解要二分的变量在实际问题中的含义，比如这里的二分变量为i，i对应了切分点的位置，而切分点有m + 1种可能，所以i的取值范围是$[0,m]$，而不是往常的m - 1为什么left_part在总序列长度为奇数时一定是更长的那一个，以至于我们可以直接在此情况下返回median1？根据我们的题解思路，left_part的总长度为$i+j=\frac{m+n+1}{2}$，一定是大于右边的长度$m-i+n-j$的（因为$\frac{m+n+1}{2}-m+i-n+j=\frac{m+n+1}{2}-m-n+\frac{m+n+1}{2}=m+n+1-m-n=1>0$，所以len(left_part)在此情况下始终>len(right_part)，且一定会长出1个元素来，这个元素就是我们要的答案）二分法一定能收敛到我们想要的那个值，因为i 的区间是 [0, m]，有限个切分点每次二分都排除了不满足的部分至少有一个合法切分存在（因为数组整体有序，左半部分的总数固定是 (m+n+1)//2，必然能切出来）用数学归纳法来对问题进行抽象，用数学公式来直接表示问题，用好数学工具结果0ms 100%, 17.78% 57.53%
题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/我的思路基本上是延续153题的思路，但和153题不一样的是，这题中可能会有重复的相同元素出现，因此需要多加思考。考虑到的可能情况为：[3,3,1,3], [10,1,10,10,10]，nums[mid] >或< nums[r]的情况比较好解决，和153中的思路一样，但当二者相等时，要如何处理呢？一开始只想到了笨方法，有灵光一现想到只要考虑右边即可（因为原数组已经是按非递减顺序排好），但没有抓住这个思路继续想下去，而是继续尝试笨方法：分情况讨论。数值相同的情况可能有几种，比如[3,3,1,3]，l在0处，r在3处，mid = 1，以及[10,1,10,10,10]，l在0处，r在4处，mid = 2，那很自然想到说要判断一下mid前后的数值情况，如果nums[mid - 1] == nums[mid]，那就从左边缩短区间，l = mid + 1，如果nums[mid + 1] == nums[mid]，那就从右边缩短区间，r = mid - 1但是，这样的思路卡在[1,1]上，mid = 0，nums[-1]仍然为1，会进入死循环。于是乎再尝试加入判断条件l - r ≠ 1，才进入这样的判断，但是又卡在了[1,1,0,1,1,1,1,1,1,1,1,1]上，起初l = 0, r = 11, mid = 5，因为条件语句首先会判断nums[mid - 1]是否和nums[mid]相等，因此在此先执行了此条判断，返回值为True，于是乎改变了l = mid + 1 = 6，直接把正确答案给略过了。这样的办法还是不行，卡在了当元素相同时的左右取舍上。于是乎又想到另一个办法，写一个子函数来判断序列的片段[l:nums+1]和[nums:r]是否都为相同元素，然后将全部为相同元素的那一边进行缩短。这样一来，整个程序又成了屎山代码，又臭又长。纠正被狠狠思维定势住了改变左右边界，不一定要基于mid来改，在这道题的情境下这样做很容易把正确答案给直接略过了，步子不要跨那么大，我每次只走1步，那样也是可以的，把r = mid - 1改成r -= 1，每次都改一点点，因为旋转前的原序列是非递减的，因此我们只需要不断改右边就好反思唉，还是得多练练结果0ms 100%, 17.91MB 62.5%
题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/我的思路经历了第34题的摧残后，这道题显得没有那么难了，拿到题目读了一下题意和要求后稍微调整了一下解法就顺利通过了，结果表现也还不错。但还是把这题记录下来，是其中有一个地方和34中不太一样，就是当nums[mid]<nums[r]时，应该将mid直接赋给r，而不是mid-1，解释：因为在这里我们要找到的时最小值，nums[mid]<nums[r]可能会存在于下面的情况：…18…3,1,2…9…，此时l位于18处，r位于9处，mid指向1，而1的前面是3，1就是我们要找的最小值了，因此不能把此时mid这个位置的元素给排除掉（我们之前mid-1就是因为从mid起，包括mid在内的右边部分全部没用了，所以才这么赋值），此时mid指向的位置就是r的最小值了，区间不能再从右边往里面缩了，之后的判断操作也只能从左边开始缩区间结果0ms 100%, 17.63MB 94.39%
34. 在排序数组中查找元素的第一个和最后一个位置
题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/我的思路大前提：序列已经按非递减顺序排列好。题目要求时间复杂度只能为$O(\log n)$，因此不能用简单的指针法（那样的复杂度为n），只能用二分法来求解。用两次二分法，第一次找第一个出现的位置，第二次找最后一个出现的位置，二分法的时间复杂度本身就为$O(\log n)$，用两次加起来$O(\log n)+O(\log n)$也仍然是$O(\log n)$target出现位置肯定满足条件nums[mid] == target，但也需要进一步判断：第一次出现位置：mid == 0 or nums[mid - 1] < target （有可能回到了列表起点），如果都不符合，那说明nums[mid - 1] = target（这个时候不可能是>target了，否则和先决条件nums[mid] == target以及非递减序列的大前提矛盾），意味着此时的mid还不够靠左，要把mid值往左边移，因此r = mid - 1最后出现位置：mid == len(nums) - 1 or nums[mid + 1] > target （有可能到了列表末尾）当nums[mid] > target时，应该缩短右侧区间，即r = mid - 1，继续做判断，当nums[mid] < target时，应该缩短左侧区间，l = mid + 1思路很明确，但是在执行的时候，还是卡在了如何更新l和r上，要么是选取不合理返不回正确的结果，要么是取值不当让程序陷入死循环纠正始终记住：mid永远在l和r的中间，l和r才是边界。区间的变化无非两种情况，可以通过判断mid值的移动趋势来执行操作，这也是二分法的核心所在：要把mid值往左移动，意味着要从右边缩小区间，因此应该改右边界r = mid - 1（如果把此时的l移动到mid或者mid-1，无论怎样都相当于把l给扩大了或者不变，扩大的情况会让mid值更大，不满足题意，不变的话就会让程序陷入死循环）在这道题里，nums[mid] > target，说明区间“往右伸”得太多了，因此肯定要从右边开始缩减，此时mid和mid之后范围的数值都没有用了，因此除开这些没用的数值，r = mid - 1，这就是-1的由来，如下图所示（注意，这里的坐标轴指的是索引，不是代表序列中的数值，target表示的是target所在的位置）要把mid值往右移动，说明要从左边缩小区间，因此应该改左边界l = mid + 1（如果把此时的r移动到mid或者mid+1，那就相当于把r给缩小了，会让mid值更往左靠，不满足题意）同样地，nums[mid] < target，说明区间“往左伸”得太多了，因此肯定要从左边开始缩减，此时mid和mid之前范围的数值都没有用了，因此除开这些没用的数值，l = mid + 1，这就是+1的由来反思一定要仔细仔细读题，充分利用好题目中的所给条件，并读懂题意，看懂要求，已经好几次没有好好利用题目里给的“非递减序列的条件了序列”的条件了要学习算法复杂度的表示方法，不然在有的题目里会有限制，看不懂培养抽象思维，将问题进行抽象表达，找到共性的特点可以让代码尽可能简单一些（当然，这是进阶要求，现阶段对自己的要求还是能顺利通过解答即可），这道题里一开始的思路是要判断两次，那会很容易想到写两个子函数，但其实这两个子函数有很大篇幅的share部分，统统单独写出来就会篇幅很长不够简洁，完全可以写到一个函数里面结果0ms 100%, 18.74MB 54.33%
题目链接：https://leetcode.cn/problems/sqrtx/description/我的思路明显的用二分法的问题，根据教材提示，已知输入为$x$，问题可转化为求$f(y)=y^2-x$的零点问题，可得$f(0)=0-x=-x<0, f(x)=x^2-x>0$，于是我们可以把初始区间定为$[0,x]$，然后开始二分。回顾一下二分的核心思想，不断缩短考察的区间，二分二分，顾名思义要取中间值$mid=(0+x)/2$，之后再判断$f(mid)$是大于0还是小于0，如果大于0，即$mid^2>x$，那就把区间设置为$[0,mid]$，如果小于0，即$mid^2<x$，那就把区间设置为$[mid,x]$，接着继续取新的二分中间值$mid_1=(l+r)/2$，这里的l和r分别代表了区间的左右边界值但是，卡在了这里，一开始只要找到了$mid^2<x$的值，就把mid作为结果返回，但后来发现这样不对，就不知道该怎么确定结果值了。这样的思路会让程序陷入死循环，或者直接返回更小的那个符合题意得值（比如x=6，二分会让程序跳到1，返回1，但应该是2），问题出在了区间的选取上，默认为闭区间，就会很容易出问题。比如x=10，那么程序运行过程如下：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = midl = 0, r = 5, mid = 2, mid^2 = 4 < 10, so l = midl = 2, r = 5, mid = 3, mid^2 = 9 < 10, so l = midl = 3, r = 5, mid = 4, mid^2 = 16 > 10, so r = midl = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = midl = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid…如此循环下去，陷入死循环，因此这样的确定l和r的方式肯定是不对的，那么如何解决呢？纠正闭区间不行，那我们就设置成开区间咯，我们一个个来试试，比如首先试左闭右开，仍以上面的例子为例，x=10，一开始仍把区间设置为$[0,10]$，但在循环过程中改成左闭右开来避免上面的问题出现。当二分到$mid^2<x$时，就把此时的mid记录为ans，如果这是最后一次二分，那么说明这个肯定是最优解。那实际该如何操作呢？因为这题里我们面对的操作对象全部是整数，因此开区间情况下，只需要把数值-1列为端点即可，比如当区间变化为$[0,5)$时，我们只需要取l = 0, r = 5-1 = 4即可，按这样的思路，我们再过一遍流程：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = mid - 1 = 4l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid, ans = 2l = 2, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid, ans = 3l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid, ans = 3…显然这样的办法还是不行，同样地，左开右闭也行不通，那就只剩全开区间了，在设置新区间时，端点全部移动1位（l+1，r-1），按这样的思路我们再来一次：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = mid - 1 = 4l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid + 1 = 3, ans = 2l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid + 1 = 4, ans = 3l = 4, r = 4, mid = 4, mid^2 = 16 > 10, so r = mid - 1 = 3l = 4, r = 3, l > r, 溢出，程序结束，ans = 3这样一来便行得通了，而且这样的方法为我们判断程序结束创造了条件，while的条件应为l≤r，当l>r时，便结束程序，输出此时的ans反思对二分的概念一定要掌握清楚绝大多数情况下，开区间还是闭区间都能找到答案，但像此题一样，有时候还是找不到解，就要尝试换一种区间模式，平时写代码时，尽可能养成习惯，如适配Python的程序规则，使用左闭右开区间结果12ms 19.54%, 17.29MB 99.16%