4. 寻找两个正序数组的中位数

题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/我的思路这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。题解官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这

二分法 · 06-04

154. 寻找旋转排序数组中的最小值 II

题目链接：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]，那

二分法 · 05-14

153. 寻找旋转排序数组中的最小值

题目链接：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%

二分法 · 05-08

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

二分法 · 05-06

69. x的平方根 

题目链接：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），问题

二分法 · 05-03