1 of 9

Please pick up your Recursion test.

You are going to implement a guessing game soon.

If you ask the user to guess a number between 1 and 1000 and your program gives the user feedback after each guess that is not correct (too high, too low), how many attempts should you give the user to ensure that the user can win as long as they make smart guesses?

Explain why in your IN.

To do: September 7

2 of 9

1. What is a requirement of the list of numbers in order to use binary search?

2. What’s the other type of search algorithm called and what is its runtime?

Binary Search

3 of 9

What is the minimum number of attempts needed to ensure you guess the correct number out of n numbers if you know the number is included in the list?

Why? You are decreasing the size of the list by half after each guess if you guess the middle number.

2. What is a requirement of the list of numbers in order to use this method of searching for a number?

List must be in order.

Binary Search

4 of 9

Describe a case when you would use linear search instead of binary search.

Binary vs Linear Search

5 of 9

boolean isHungry, isTired;

// assignment of variables not shown

What is equivalent to the following compound boolean expression?

!(isHungry || isTired) == ?

!(isHungry && isTired) == ?

Compound Boolean Expressions

6 of 9

boolean isHungry, isTired;

// assignment of variables not shown

What is equivalent to the following compound boolean expression?

DeMorgan’s Law

!(isHungry || isTired) ==

!isHungry && !isTired

!(isHungry && isTired) ==

!isHungry || !isTired

Compound Boolean Expressions

7 of 9

MC
FRQ sol/rubric
Revised syllabus

�

Go over test

8 of 9

Implement binary search using iteration on the white board.

Once you're done, copy in your IN.

public int binarySearch (int [] nums, int val)

{

}

Binary search: iterative

9 of 9

Homework

Repl.it lab - Test 1-1 required for everyone
Complete Test corrections to Hub - for each problem missed:

Summarize the question in your own words
Write out work to show how to get to correct answer
Explain your misunderstanding
Submit to Hub