| | 1 | === Binary Searching === |
| | 2 | |
| | 3 | Sometimes, you may be asked to narrow the list of possible revisions. |
| | 4 | The quickest way to do this is a 'binary search'. |
| | 5 | In short, a binary search involves testing the middle value to see which half of the data contains the answer. |
| | 6 | 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'. |
| | 7 | |
| | 8 | Here is an example: revision 38000 fails to boot, last known good revision is 34000. |
| | 9 | |
| | 10 | 1. Pass One |
| | 11 | * middle = 36000 (38000 - 34000) |
| | 12 | * boot = success |
| | 13 | * the issue is somewhere between 36000 and 38000 |
| | 14 | * you eliminated 2,000 possible revisions |
| | 15 | 1. Pass Two |
| | 16 | * middle = 37000 |
| | 17 | * boot = success |
| | 18 | * the is somewhere between 37000 and 38000 |
| | 19 | * you eliminated another 1,000 possible revisions as not-containing the error. |
| | 20 | 1. Pass Three |
| | 21 | * middle = 37500 |
| | 22 | * boot = failure |
| | 23 | * the is somewhere between 37000 and 37500 |
| | 24 | * another 500 revisions (3,500 in total) are now known to be "good" |
| | 25 | 1. Pass Four |
| | 26 | * middle = 37250 |
| | 27 | * boot = success |
| | 28 | * the is somewhere between 37250 and 37500 |
| | 29 | * Diminishing returns starts kicking in; only an extra 250 revisions were eliminated |
| | 30 | 1. Pass Five |
| | 31 | * middle = 37375 |
| | 32 | * boot = failure |
| | 33 | * the is somewhere between 37250 and 37375 |
| | 34 | By testing 5 revisions, the range has been reduced from 4,000 to a more manageable 125! |
