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.

1. Pass One
   • middle = 36000 (38000 - 34000)
   • boot = success
   • the issue is somewhere between 36000 and 38000
   • you eliminated 2,000 possible revisions
2. Pass Two
   • middle = 37000
   • boot = success
   • the 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 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 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 is somewhere between 37250 and 37375

By testing 5 revisions, the range has been reduced from 4,000 to a more manageable 125!