Changes between Version 1 and Version 2 of BinarySearch


Ignore:
Timestamp:
May 6, 2010, 8:35:32 AM (9 years ago)
Author:
mmadia
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BinarySearch

    v1 v2  
    66As 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'.
    77
    8 Here is an example: revision 38000 fails to boot, last known good revision is 34000.
     8Here is an example: revision 38000 fails to boot, last known good revision is 34000. That's a whopping 4,000 revisions to consider!
    99
    1010 1. Pass One
     
    1212   * boot = success
    1313   * the issue is somewhere between 36000 and 38000
    14    * you eliminated 2,000 possible revisions
     14   * you just eliminated 2,000 possible revisions with a single test!
    1515 1. Pass Two
    1616   * middle = 37000
    1717   * boot = success
    18    * the is somewhere between 37000 and 38000
     18   * the offending changeset is somewhere between 37000 and 38000
    1919   * you eliminated another 1,000 possible revisions as not-containing the error.
    2020 1. Pass Three
    2121   * middle = 37500
    2222   * boot = failure
    23    * the is somewhere between 37000 and 37500
     23   * the problem is somewhere between 37000 and 37500
    2424   * another 500 revisions (3,500 in total) are now known to be "good"
    2525 1. Pass Four
    2626   * middle = 37250
    2727   * boot = success
    28    * the is somewhere between 37250 and 37500
     28   * the error is somewhere between 37250 and 37500
    2929   * Diminishing returns starts kicking in; only an extra 250 revisions were eliminated
    3030 1. Pass Five
    3131   * middle = 37375
    3232   * 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!
     33   * the issue is somewhere between 37250 and 37375
     34
     35By 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.