Algorithms ⇫ Up
Previous Page ⇦ Multiple Sensor Reading
• You want to perform a binary search through an ordered array of possibilities.
• Each of the items in the array to evaluate for "pass" or "fail" needs a long time.
• You want to find the highest value that is a "pass".

Example, you have a bug in revision 312 of your code. You know it was ok at revision 289. What is the highest revision that passes? Say it takes 5 minutes to check each revision.

e.g. say there are 3 developers (i.e. "threads") A, B, C

``` set 2 variables currentLow and currentHigh (289 and 312 respectively)
set B to search at midpoint between currentLow and currentHigh
set A to search at midpoint between currentLow and B
set C to search at midpoint between B and currentHigh

loop until done
TODO: when does it stop?
TODO: what if currentLow and currentHigh are only 1 or 2 apart?
TODO: check if does values at currentLow and currentHigh?

if A fails
Stop B & C immediately
set currentHigh to A
A, B, C choose again

if B fails
Stop C immediately
(A continues)
set currentHigh to B
rename A as "B" (so B is always the middle one)
A chooses midpoint between currentLow and B
C chooses midpoint between B and currentHigh

if C fails
Stop A & B immediately
set currentLow to C
A, B, C choose again

if A passes
Set currentLow to A
Set A to midpoint between currentLow and B

if B passes
Stop A immediately
(C continues)
set currentLow to B
set B to midpoint between currentLow and C
set A to midpoint between currentLow and B

if C passes
Stop A & B immediately
Set currentLow to C
All three choose again
```