处理二分查找变体的心理框架

Question

我需要某种心理框架来实现需要二进制搜索的解决方案。我不知道我错过了什么，但我似乎不能自己想出一个解决方案。让我们以下面的问题为例，但我的问题是更一般的问题，涉及二分查找。

目的:给定一个非负整数x，计算并返回x的截去小数点的平方根。注意，不能使用幂函数或sqrt函数

的例子:

• input = 8
• 输出= 2
• 解释，8的平方根是2.82..，但我们只关心整数，所以返回2

问题描述我目前的方法是写下大约3-4个测试用例，并应用我最熟悉的二进制搜索。由leetcode文档为"模板1";https://leetcode.com/explore/learn/card/binary-search/125/template-i/938/

然后我尝试修改它，使那些测试用例通过。这感觉像是一种非常幼稚的方法，而且显然不是这种方法，因为我总是无法提供解决方案，因为不是所有的测试用例都通过了，甚至对于其他二进制搜索样式的问题也是如此。

# passes x = 6, x = 4, x = 3. Fails x = 2, x = 7
class Solution:
def mySqrt(self, x: int) -> int:

if x == 0:
return x
if x == 1:
return 1

lo = 0
hi = x-1

while lo <= hi:
mid = lo + (hi - lo)//2
val = (mid + 1) * (mid + 1)

if val < x:   # we are looking too low
lo = mid + 1
elif val > x:   # we are looking too high
hi = mid - 1
else:
return mid + 1

return mid + 1

• 应该采取什么方法来解决这类问题?
• 此外，我遇到了这个问题的不变量的麻烦。会是什么呢?

Answer 1

你很接近，但是有些细节是错误的。看起来你并没有真正理解二分查找是如何工作的。

尤其考虑到比较mid * mid和x可以告诉你mid是否太高，但它不能告诉你mid是否太低，或者刚刚好。没关系。你只需要小心使用你从比较中得到的信息，就像这样:

mySqrt(x: int) -> int:
lo = 0  # lowest possible answer
hi = x  # highest possible answer
while lo < hi:
# we have not yet determined the answer
# this guarantees lo <= mid-1 < mid <= hi
# I wrote this line *after* writing the conditions below that
# produce mid-1 and mid as new boundaries.
mid = lo + (hi + 1 - lo)//2
if mid*mid > x:
# mid is too high
hi = mid-1  # new highest possible answer
else:
# mid is not too high
lo = mid    # new lowest possible answer
# here hi = lo, so we know what the answer is
return lo

。

注意如果我们有&;too low&;测试而不是"太高"测试，然后我们将得到mid和mid+1作为可能的新边界，我们将调整我们设置mid的行，以确保它们都在[lo,hi]范围内，如mid = lo + (hi-lo)//2。