Name:
Navigate to Level 1 in Code Studio.
Use the ticket generator to generate seven tickets. Put the numbers onto sticky notes.
Organize the ticket numbers in numerical order from least to greatest.
Copy one of the numbers onto a separate sticky note and think.
How would you search for that number in the list?
You could search for that number in an if-else statement. If numticket=235 then display you win else you lose. |
Create an algorithm to determine if a number is in a list of sorted numbers. Consider the following
Go to the middle of the list and then check from the middle (4th number) checking down or up depending if your number is higher or lower than the middle number. |
Try this algorithm
How does it compare to the algorithm you created?
The number that I chose was the middle number so I only had to do 1 step. |
Tell how many steps are needed for each amount of inputs using a binary search algorithm (fill in the missing values)
Note: The number of inputs is the number of sticky notes you might have.
inputs | steps | |
Instance | 1 | 1 |
Instance | 3 | 2 |
Instance | 5 | 3 |
Instance | 7 | 3 |
Instance | 9 | 4 |
Instance | 15 | 4 |
If I had one input, which algorithm would I use to get my answer with the fewest amount of steps?
Binary or Linear |
What if I had five?
Binary search must be sorted and starts at the middle |
What about one hundred?
Binary search must be sorted |