STEM Sims Logo
PDF Lesson

Lessons 3: Binary Search

Assuming that there is only one source of contamination, another way to find the egg contamination is to break up the number of items you’re searching through into two groups. This is called a binary search. For the first round, you will search three of the coops. If a contamination is found, you have narrowed down the possible coops to those three. If a contamination is not found, you have eliminated those three coops, and the remaining two coops are the possible contaminated coops. If you repeat the process you will eventually be led to the contaminated coop. Are you ready for the binary search egg-sercise?

Doing the science

  1. Start the Egg Sampling Simulation by clicking on the "Sim" tab.
  2. Record in Table 1 the starting code provided as the simulation started.
  3. Click on the "Start Sim" button.
  4. Click on letters A, B, and C of the chicken coops to get eggs. Collect more eggs from these coops by clicking on the letter multiple times. Record the letters into Table 1 below.
  5. Click on the "Lot Code" button and record the lot code provided into the table.
  6. Click on the "Egg Prep Center" button.
  7. Click on the "DeSheller" box to deshell the eggs, then click on the "Mixer" box to mix them.
  8. Add "KI/I" by clicking on the bottle.
  9. Drag and drop the eggs into the "Incubator 9000".
  10. Click on the "Start" button to begin the timer.
  11. Drag the pH meter to the eggs to test the pH level.
  12. Click on "HCl" or "NaOH" to change the pH of the eggs to a pH of between 6.6 and 7.0.
  13. Drag the pH meter back onto the shelf.
  14. Drag and drop the eggs back into the "Incubator 9000".
  15. Click on the "Start" button to begin the timer.
  16. Click on "Egg Test Center".
  17. Click on each test reagent (1-6) to add the reagents to the egg sample.
  18. Click on "Results" to see if the test reagents changed.
  19. Analyze the results by clicking on "Egg Test Database" and comparing the colors of the test tubes to the database. Record if the test tube stayed the same, has +Bacteria, or has –Bacteria.
  20. Repeat steps 4-19 with the remaining chicken coops that you need to test (either A, B, C or D, E). If you need to test A, B, and C, remember you can further split that up by testing A, B or C.
  21. When you find the source of the contamination, enter the coop letter into the table.

Table 1.

Starting Code:

Eggs from:

Lot Center:

Urease Test

Lysine Decarboxylase

Malonate Broth Test

Phenol Red Sucrose Broth Test

Voges-Proskauer Test

Methyl Red Test

Egg Contamination Source: Coop

Do You Understand?

  1. Although this simulation only has five chicken coops, what would happen if there were thousands of chicken coops?

  2. How does a binary search compare to a linear search? Which is faster?

  3. Why would a binary search not work for multiple instances of contamination?

  4. What similar methods would you be able to use if there were 100 chicken coops but five contaminated coops?

  5. Can you think of another method to find a contaminated coop?