5.03 Search Algorithms

5.3 Search Algorithms Curriculum Page

Portfolio Reflection Questions:

1. (POGIL) Define a pseudocode algorithm that will efficiently play the guessing game.

• Last guess is = highest number/2

Guess the last number

If guess too low

Guess (highest-last)/2 + (highest/last)

Else if guess to high

Guess (highest-last)/2

2. (POGIL) To guess a number between 1 and 100, what's the maximum number of guesses your algorithm would take?

• 7 guesses
• because log2100= 6.6438 (round to 7)

3. (POGIL) To guess a number between 1 and 500, what's the maximum number of guesses your algorithm would take?

• 9 guesses
• because log2500 = 8.9657 (round to 9)

4. Suppose you have a deck of cards and you want to find the Ace of Spades. If the deck is shuffled, which is the best search algorithm to use and why?

• The best algorithm to find the Ace of Spades in a shuffled deck is linear search because the cards will be out of order so there won't be a more efficient algorithm. (linear search best for unordered lists and binary lists best for ordered lists)

5. Give an example of a search problem you encounter in everyday life. Do it use sequential, binary, or some other search?

• A search problem I encounter in everyday life is searching for people's contacts based on their name. Most of the time I use linear search since the last names are in order from A to Z, so I'll just search by alphabetical order. Also, sometimes I'll search the names by doing a filter search. (ie. typing in first few letters of last name)