二分查找 - 一周思进

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

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

FEATURED TAGS