ARTS-WEEK11

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)

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

    res =  round(mid)
    if (res * res) > x:
        return int(mid)
    else:
        return round(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