def merge_sort left right None if right is None right len if right lef

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def merge_sort(a, left=0, right=None):
if right is None:
right = len(a)
if right - left > 1:
middle = (left + right) // 2
merge_sort(a, left, middle)
merge_sort(a, middle, right)
merge(a, left, middle, right)
def merge(a, left, middle, right):
first = a[left:middle]
second = a[middle:right]
i = j = 0
for k in range(left, right):
if i < len(first) and (j == len(second) or first[i] <= second[j]):
a[k] = first[i]
i += 1
else:
a[k] = second[j]
j += 1
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))