Multithreaded Binary Search

	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.

Instead of one thread going through the array, have multiple threads.

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