10.2 Recursive Searching and Sorting

Enduring Understanding

Programmers incorporate iteration and selection into code as a way of providing instructions for the computer to process each of the many possible input values.

Learning Objective

Apply recursive search algorithms to information in String, 1D array, or ArrayList objects.

Essential Knowledge

Data must be in sorted order to use the binary search algorithm.

The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each iteration until the desired value is found or all elements have been eliminated.

Binary search can be more efficient than sequential/linear search.

Search algorithms other than sequential/linear and binary search are outside the scope of the course and AP Exam.

The binary search algorithm can be written either iteratively or recursively.

Apply recursive algorithms to sort elements of array or ArrayList objects.

Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.