Binary search

First, step through a specific problem, then, generalize to any problem.

Specific Problem, looking for the number 19 Generalization, looking for any value in any array
  1. Search through the array of int vals =
    { 1, 2, 3, 4, 6, 9, 10, 11, 12, 14, 15, 17, 18, 19, 20};
  2. What is the length of the array?
  3. What is the position of the first value?
  4. What is the position of the last value?
  5. Where is the middle of the values you are looking through?
    What number is in the middle?
  6. Compare your number to the middle value, are you too low, too high or just right?
  7. Fill in the table below:
    index of low index of high middle position middle value low high or just right?
             
             
             
             
  1. How do you declare an array of integers?
    __________________________________________
  2. Find the length of the array
  3. What is the position of the first value?
  4. What is the position of the last value?
  5. What is the equation to find the middle of the values you are looking through?
    ___________________________________________
  6. Write the if statement to see if you're too low, too high or just right
    if(_______________________)
    //too low
    else if (__________________________)
    // too high
    else return ______
    // just right
  7. How do you calculate the new low and high indices if:
    • the value checked is too low
      low = ______, high = ____
    • the value checked is too high
      low = ______, high = ____

 

Challenge: How do you change the routine to work for Strings? copy and rewrite it, use compareTo.