二分

二分的本质是二段性（注意：可二分的数组不一定要有序）

有序数组具备二段性，我们选择一个数可以将该有序数组分为两部分，一部分是满足条件的，另一部分是不满足条件的（比如：选择条件为小于等于）

整数二分

从左边开始查找

# 查找条件存在于左边界 比如 target <= nums[mid], 从左边开始查找
def l_bin_search(left: int, right: int):
    while left < right:
        mid = left + ((right - left) >> 1)
        if check(mid):
            right = mid
            continue
        left = mid + 1
    return left

从右边开始查找

# 查找条件存在于右边界 比如 target >= nums[mid], 从右边开始查找
def r_bin_search(left: int, right: int):
    while left < right:
        mid = left + ((right - left + 1) >> 1)    # 注意此处需要进行+1操作否则有些case会陷入死循环
        if check(mid):
            left = mid
            continue
        right = mid - 1
    return left

练习

x的平方根

有效的完全平方数

在排序数组中查找元素的第一个和最后一个位置

搜索插入位置

浮点数二分

利用浮点数二分求平方根

# 利用浮点数二分求平方根

def sqrt(x):
    left = 0
    right = x
    mid = 0
    while right - left > 1e-8:
        mid = left + ((right - left) / 2)
        if mid * mid >= x:
            right = mid
        else:
            left = mid

    print(mid)

数的三次方根

# 需要注意处理负数
xx = float(input())

def r3(x):
    left = 0
    right = x
    mid = 0
    while right - left > 1e-8:
        mid = left + ((right - left) / 2)
        if mid * mid * mid >= x:
            right = mid
        else:
            left = mid
    return mid

flag = False
if xx < 0:
    xx = -xx
    flag = True

mid = r3(xx)
if flag:
    mid = -mid
print('%.6f' % mid)