# 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.