Binary Searching

Sometimes, you may be asked to narrow the list of possible revisions. The quickest way to do this is a 'binary search'. In short, a binary search involves testing the middle value to see which half of the data contains the answer. As you repeat this test, the range of possible revisions shrinks by half each time. To note, some version control systems such as hg and git call it 'bisect'.

Here is an example: revision 38000 fails to boot, last known good revision is 34000. That's a whopping 4,000 revisions to consider!

1. Pass One
   • middle = 36000 (38000 - 34000)
   • boot = success
   • the issue is somewhere between 36000 and 38000
   • you just eliminated 2,000 possible revisions with a single test!
2. Pass Two
   • middle = 37000
   • boot = success
   • the offending changeset is somewhere between 37000 and 38000
   • you eliminated another 1,000 possible revisions as not-containing the error.
3. Pass Three
   • middle = 37500
   • boot = failure
   • the problem is somewhere between 37000 and 37500
   • another 500 revisions (3,500 in total) are now known to be "good"
4. Pass Four
   • middle = 37250
   • boot = success
   • the error is somewhere between 37250 and 37500
   • Diminishing returns starts kicking in; only an extra 250 revisions were eliminated
5. Pass Five
   • middle = 37375
   • boot = failure
   • the issue is somewhere between 37250 and 37375

By testing 5 revisions, the range has been reduced from 4,000 to a more manageable 125! If you wanted, you could keep repeating this to narrow the range to 63, 32, or even 16 revisions. Depending on the error and the neighboring commits, you may need to reduce it even further.