二分查找常用场景就是针对已排序的数组进行搜索,下面是代码实现:
def bsearch(list, num):
low = 0
high = len(list) - 1
while(low <= high): # 注意要包含等于,否则如果只有一个的情况下,还需要单独写if语句
mid = low + (high-low) // 2 # 这里注意不要写成 (low+high) // 2,否则可能溢出,也可以写成 low + (high-low) >> 2
if list[mid] == num:
return mid
elif list[mid] < num:
low = mid + 1
else:
high = mid - 1
return -1
# 递归实现
def bsearch_recursion(list, l, r, num):
if (l > r):
return -1
mid = l + (r-l) // 2
if (list[mid] == num):
return mid
elif list[mid] < num:
return bsearch_recursion(list, mid+1, r, num)
else:
return bsearch_recursion(list, l, mid-1, num)
LeetCode 对应练习:
https://leetcode-cn.com/problems/sqrtx/
然而自己并没有理解二分查找的精髓啊,实现的方式实际并没有套用二分查找的模板来写,也仍旧忘记考虑溢出的可能… 代码如下:
ABS_GAP = 1e-10 # print("%.10f"%(ABS_GAP)) 默认小数点后面保留6位
class Solution:
def mySqrt(self, x: int) -> int:
if (x == 1):
return 1
mid = x / 2
y = x
while (abs((mid*mid - x)) > ABS_GAP):
if (mid * mid > x):
y = mid
mid = mid / 2
else:
mid = (mid + y) / 2
return int(mid)
按二分查找模板改写后:
ABS_GAP = 1e-10 # print("%.10f"%(ABS_GAP)) 默认小数点后面保留6位
class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x
if (0 == x or 1 == x):
return x
while (l <= r):
mid = l + (r-l) / 2
if (abs(mid - x/mid) <= ABS_GAP): # mid*mid -x 比较可能会越界
return int(mid)
elif (mid > x / mid):
r = mid
else:
l = mid
但是测试发现,mid 打印虽然显示是6.0000000000,int转换之后却是5了,将小数点保留位数扩大后,再重新打印mid,发现值是5.99999999999454303
了解了下 python 浮点数转整数的四种操作运算 int、round、ceil、floor,其中 int 是向0取整,round是四舍五入,math.floor是向下取整,math.ceil向上取整
增加了如下判断后,提交通过…
res = round(mid)
if (res * res) > x:
return int(mid)
else:
return round(mid)
当然看了官方题解,其实完全不用按浮点数来计算比较的,就是需要注意小于情况下需要保存当前的mid值,以便循环条件不满足时返回,代码如下:
class Solution:
def mySqrt(self, x: int) -> int:
l = 1
r = x
res = 0
y = 0
while (l <= r):
mid = l + (r-l) // 2
y = mid * mid
if (y == x):
return mid
elif (y > x):
r = mid - 1
else:
res = mid
l = mid + 1
return res