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

The search can start at any of the sticky notes
You can "jump" over sticky notes. In other words, you don't need to search for the stickies in order.
You can determine which sticky notes to search next based on the current sticky note you are checking.
The goal is to make the determination in the least steps possible, but don't forget your number could be anywhere in the list - what is the worst possible case? What is the greatest number of comparison steps it would take to find any number in your list using your current algorithm?

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

Find the middle number in the list. Compare that number to the given number. If the number is less than the given number, remove all of the cards to the right (including the middle number). If the number is more than the given number, remove all of the cards to the left (including the middle number).
Find the middle number in this shorter list. Follow the instructions in Step #1 for comparing.
Find the middle number in this new shorter list. Follow the instructions in Step #1 for comparing.

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