二分查找

Posted by 周思进 on August 23, 2020

二分查找常用场景就是针对已排序的数组进行搜索,下面是代码实现:


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