lower_bound, upper_bound
def lower_bound(input_list, target_value):
if not input_list:
return 0
lo, hi = 0, len(input_list)
while lo < hi:
mid = (lo + hi) // 2
if input_list[mid] < target_value:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(input_list, target_value):
if not input_list:
return 0
lo, hi = 0, len(input_list)
while lo < hi:
mid = (lo + hi) // 2
if target_value < input_list[mid]:
hi = mid
else:
lo = mid + 1
