def bisect_right(a, x):
left, right = 0, len(a)
# [left; right)
while right - left > 1: # until [left, right) == {x}
assert (x not in a) or (x in a[left:right])
mid = (left + right) // 2
print(mid)
if a[mid] <= x:
left = mid
else:
right = mid
if a[left] == x: # why not m?
return left
else:
return None
def bisect_left(a, x):
left, right = -1, len(a) - 1
# (left; right]
while right - left > 1: # until (left, right] == {x}
#assert (x not in a) or (x in a[left+1:right+1]) # x in (left; right]
mid = (left + right) // 2
print(mid)
if a[mid] < x:
left = mid
else:
right = mid
print(right)
if a[right] == x: # why not m?
return right
else:
return None
a = [3, 4, 5, 6, 8, 7, 9, 10]
print(bisect_left(a, 8))
#a = [1, 3, 4, 4, 4, 5, 6, 6]
#print(bisect_right(a, 4))