Binary Search
Pre-work
- In Barron's AP Computer Science A, read about Binary Search on p. 329-330.
- Optional: Read about binary search in another text book that will be made available to you in class.
- Study and execute these Java implementations of binary search.
- Read the multiple choice questions on sorting and searching on pp. 331-345 of Barron's AP Computer Science A. Attempt to answer the questions that are related to binary search and then check your answer(s) using the answers provided on pp. 346-350.
Questions
- [1 point] Which questions in Barron's AP Computer Science A (pp. 331-345) involve or are related to binary search? List the question numbers only.
- [1 points] What is the difference between the Java implementations of binary search that implement Search<T> and the ones that implement MeteredSearch<T>?
- [2 points] Compare and contrast RecursiveBinarySearch and RepetitiveBinarySearch.
Create Activity
- [3 points] Create a multiple choice question about binary search. You question should include five choices (a - e) for the answer and only one correct answer. Your question may be inspired by a question from Barron's AP Computer Science A but must be substantially different, i.e. you should feel confident that no one would ever accuse you of plagiarizing the question.
- [6 points] Create two implementations of RecursiveBinaryMeteredSearch or RepetitiveBinaryMeteredSearch that are different from the ones provided. (Consider replacing the switch statement with if-else statements or calculating the value of middle differently.) Both implementations must compile and must implement MeteredSearch<T>. One implementation should be correct (to the best of your knowledge) and the other implementation should be flawed.
- [3 points] Indicate which of the two implementations of binary search that you are submitting is flawed and describe the flaw.
