AP Computer Science A · Lesson 4.19 · Unit 4 · CED topic 4.17

Recursive traversal and binary search

Name:   Date:  

1 Why this lesson matters

Read the opening paragraph and the "Required content" box on the lesson page. In your own words, explain each objective below.

17.A. Determine the result of executing recursive algorithms that use strings or collections.

17.B. Determine the result of each iteration of a binary search algorithm used to search for information in a collection.

17.C. Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

2 Recursive traversal

Read this section. In your own words, summarize the main idea.

3 Binary search

Read this section. In your own words, summarize the main idea.

4 The same algorithm with a loop

Read this section. In your own words, summarize the main idea.

5 Why it is faster

Read this section. In your own words, summarize the main idea.

6 Worked example

Read the "Worked example" box. Then, without looking back, try writing your own answer below.

Search for 23 in {2, 5, 8, 12, 16, 23, 38} (indexes 0 to 6).

7 Exam focus: avoid this mistake

Read the "Exam focus" box, then restate it in your own words.

8 Sum it up

In two or three sentences, explain this lesson's main idea to someone who has not read it.