python实现lower_bound和upper_bound

佚名 6年前 (2018-11-29) 算法 1706人围观抢沙发百度已收录

由于对于二分法一直都不是很熟悉，这里就用C++中的lower_bound和upper_bound练练手。这里用python实现

lower_bound和upper_bound本质上用的就是二分法，lower_bound查找有序数组的第一个小于等于目标数的，upper_bound查找有序数组第一个大于等于目标数的

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

下面是python实现的lower_bound代码

def lower_bound(arr,target,i,j):
        while i < j:
                mid = i + (j - i) / 2
                mid = int(mid)
                if target > arr[mid]:
                       i = mid + 1
                else:
                        j = mid
        return mid

upper_bound的python代码

def upper_bound(arr,target,i,j):
        while i < j:
                mid = int(i + (j - i) / 2)
                if target > arr[mid]:
                        i = mid + 1
                else:
                        j = mid
                print(mid)
        return mid