由于对于二分法一直都不是很熟悉,这里就用C++中的lower_bound和upper_bound练练手。这里用python实现
lower_bound和upper_bound本质上用的就是二分法,lower_bound查找有序数组的第一个小于等于目标数的,upper_bound查找有序数组第一个大于等于目标数的
下面是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