CS2 Lesson 19: Searching

  1. Guessing Game
    1. Strategy
    2. Binary Search
    3. Running Time
    4. Finder / Code
  2. Exercise
  3. Upcoming

Guessing Game

For this lesson, you will be working on this Guessing Game / Finder activity. You’ll be going through the following steps for today:

  1. Copy/paste the starter code for GuessingGame.java.
  2. Run main. This is a guessing game where you guess a number between 0 and 1022 (inclusive). You should be able to guess the number within at most 10 guesses. Find a good strategy for this!
  3. Determine the algorithm used for (1). Then see if you can use that same idea to find an algorithm to find a number in a sorted list.
  4. Determine the running time of this “find” method. Use Big Oh notation.
  5. Use the algorithm devised in (2) to implement a faster “find” algorithm in the Finder class (included in this same starter code page). You do not need to submit this.

The lesson is mostly self directed, and so I am not including notes here, but we will be discussing these in class. For reference, when you wish to review the lesson, you can take a look at the following videos. They were from a previous version of the course when I used different software instead of VSCode (IntelliJ and/or CodingRooms). Please use the videos for help if you get stuck on any of these parts.

Strategy

Running Time

For this, you will need to have gone through the sections on Analysis of Algorithms and Big Oh. Please review those notes.

Finder / Code

Exercise

  1. If we have an unsorted list of 1 million integers, about how many comparisons would need need to determine if a number $x$ is in the list? 10, 20, 100, 1000, or 1,000,000? What algorithm would we use?
  2. If we have a sorted list of 1 million integers, about how many comparisons would need need to determine if a number $x$ is in the list? 10, 20, 100, 1000, or 1,000,000? What algorithm would we use?

Upcoming