题目链接：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 = mid
- l = 0, r = 5, mid = 2, mid^2 = 4 < 10, so l = mid
- l = 2, r = 5, mid = 3, mid^2 = 9 < 10, so l = mid
- l = 3, r = 5, mid = 4, mid^2 = 16 > 10, so r = mid
- l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid
- l = 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 = 4
- l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid, ans = 2
- l = 2, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid, ans = 3
- l = 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 = 4
- l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid + 1 = 3, ans = 2
- l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid + 1 = 4, ans = 3
- l = 4, r = 4, mid = 4, mid^2 = 16 > 10, so r = mid - 1 = 3
- l = 4, r = 3, l > r, 溢出，程序结束，ans = 3
这样一来便行得通了，而且这样的方法为我们判断程序结束创造了条件，while的条件应为l≤r，当l>r时，便结束程序，输出此时的ans
反思
- 对二分的概念一定要掌握清楚
- 绝大多数情况下，开区间还是闭区间都能找到答案，但像此题一样，有时候还是找不到解，就要尝试换一种区间模式，平时写代码时，尽可能养成习惯，如适配Python的程序规则，使用左闭右开区间
结果
12ms 19.54%, 17.29MB 99.16%
