None of your comments mention running the full test suite, only build.
When I've used bisection, I've always had a targeted test that I was trying to fail, not the entire test suite. This is because the test suite at the time of that commit wasn't good enough to detect this failure. Otherwise it would have failed with that commit.
Instead, a new failure mode is detected, an automated test developed, and that used to probe the history to identify the commit.
Why are your bisections doing the full suite?
> Black reformatting causes more steps in bisecting
Yes, of course it does. But it's log2(n).
The worst-case analysis I did assumed there was a black commit after every human commit. This is a bad practice. You should be using black as a pre-commit hook, in which case only your new collaborator's commits will cause re-formats. And once they are onboard, you can explain how to use requirements.txt in a virtualenv.
If only 10% of the commits are black reformattings, which is still high!, then a bisection of 100 human commits (plus 10 black commits) goes from about 6.64 tests to 6.78 tests, which with a 5 minute test suite takes an additional 42 seconds.
If it's 3% then your bisection time goes up by 13 seconds.
If you are so worried about 13 seconds per bisection then how much time have you spent reducing the 5 minute test suite time? I presume you run your test suite before every commit, yes? Because if not, and you're letting CI run the test suite, then you're likely introducing more commits to fix breaking tests than you would have added via black, and taking the mental task switch hit of losing then regaining focus.