Annotated version of a multi-bisect algorithm finding all places where "performance became worse" in a commit list.

multibisect.py

import numpy as np

#perf = [10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2]
perf = np.concatenate([4*np.ones(25), 2*np.ones(25), np.ones(25)])
#perf = list(range(40, 0, -1))

count = 0
def worseCommit(a, b):
    global count
    count += 1
    return perf[a] > perf[b]

def find_true(l):
    ixs = []
    last = l[0]
    for (i, e) in enumerate(l):
        if abs(e-last) > 0:
            ixs.append(i)
        last = e
    return ixs

def in_section(n, a=0, b=-1):
    if b < 0:
        b = n-1

    if worseCommit(a, b):  # there is at least one worsening in the range.
        print(f'worse commit in [{a}, {b}]')
        if abs(b-a) == 1:  # down to two commits: a better than b
            print(f' found! {b}')
            return [b]
        # range larger than 1
        mid = int((a+b)/2)  # bisect range
        # search in either range and merge.
        left = in_section(n, a, mid)
        right = in_section(n, mid, b)
        return left+right
    else:
        print(f'good commits in [{a}, {b}]')
    return []


print(in_section(len(perf)))
print(f'took {count} calls ({len(perf)} commits)')
print(find_true(perf))