31 def binary_search(ls, v):  argument
32     """Take a list ls and a value v such that ls is sorted and v is comparable
33     with the elements of ls.
37     1. ls.insert(i, v) is sorted
38     2. ls.insert(j, v) is not sorted for j < i
42     if not ls:
48     if v <= ls[0]:
55     hi = len(ls)
58         if v > ls[mid]:
64         # elif v == ls[mid]:
67             # Either v == ls[mid] in which case mid is a valid insertion point
68             # or v < ls[mid], in which case all valid insertion points must be
78 def is_sorted(ls):  argument
80     for i in range(len(ls) - 1):
81         if ls[i] > ls[i + 1]:
99 @given(ls=SortedLists, v=Values)
100 def test_insert_is_sorted(ls, v):  argument
104     ls.insert(binary_search(ls, v), v)
105     assert is_sorted(ls)
108 @given(ls=SortedLists, v=Values)
109 def test_is_minimal(ls, v):  argument
112     for i in range(binary_search(ls, v)):
113         ls2 = list(ls)
118 @given(ls=SortedLists, v=Values)
119 def test_inserts_into_same_place_twice(ls, v):  argument
133     i = binary_search(ls, v)
134     ls.insert(i, v)
135     assert binary_search(ls, v) == i