Skip to content

Instantly share code, notes, and snippets.

@m00nlight
Last active December 5, 2022 21:13
Show Gist options
  • Save m00nlight/0f9306b4d4e61ba0195f to your computer and use it in GitHub Desktop.
Save m00nlight/0f9306b4d4e61ba0195f to your computer and use it in GitHub Desktop.
Python naive implementation of lower_bound and upper_bound
def lower_bound(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) / 2
if nums[mid] >= target:
r = mid - 1
else:
l = mid + 1
return l
def upper_bound(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) / 2
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return l
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment