version control – Can I do exponential binary search, or open-interval git bisect?


git bisect is great to locate the commit that introduced a bug. You just need to know a good commit where the bug is not present, a (newer) bad commit where it is present, and a method to test whether the bug is present in any given commit. Then git bisect guides you through a binary search.

I’m interested in the situation where I don’t know a good commit. I’m assuming that there is one in the past, but I just don’t remember it. Finding it out manually is a huge manual labour that I want to avoid.

Can I run git bisect in a way such that I don’t need to specify a good commit? Can it find a good commit for me?

I’m surprised this problem isn’t well-known. I run into it every month.

One approach might be taking the first commit of the repository and marking that as good. But this has a number of problems.

The standard solution to such a problem is exponential search. The good commit is located by going to HEAD~1, then HEAD~2, HEAD~4, HEAD~8 and so on until a good commit is encountered. This also works in logarithmic time and is much better than going backwards through all the history, because we start with commits to which our testing method will probably apply well.

Is exponential search implemented for git bisect? Are there helper scripts that do it? How do you solve this problem?