找上边界:
def upper_bound(nums,target):
if nums==[]:
return -1
else:
l=0
r=len(nums)
while(l<r):
mid=(l+r)//2
if nums[mid]<=target:
l=mid+1
else:
r=mid
return l if l!=len(nums) else -1
注:最后返回的结果是l,所以需要判断l的值是否会越过数组的上界
找下边界:
def lower_bound(nums,target):
if nums==[]:
return -1
else:
l=0
r=len(nums)
while(l<r):
mid=(l+r)//2
if nums[mid]>=target:
r=mid
else:
l=mid+1
return l-1
注:最后返回的结果是l-1,如果l=0那么结果为-1。
总结
对于普通的二分查找,左右区间都是闭区间,因为要查找所在数的索引位置,而对于找数的上下界问题,区间都是开区间,找上边界,在<=目标值时,让左边界=索引位置+1,不断地逼近上界,找下边界,在>=目标值时,让右边界=索引位置。