What is the time complexity?

Answer: O(n log n) Mergesort divides log n levels and merges O(n) per level: O(n log n).

What is the worst-case time complexity?

Answer: O(log n) Binary search halves the search space each step, giving O(log n).

Why might binary search fail on this array?

Answer: The array is not sorted Binary search requires the array to be sorted; this array is not.

AP Computer Science A · Topic 10.2

Recursive Searching and Sorting (Binary Search, Merge Sort) Practice

Part of Recursion.

Practice questions

Want a predicted score for the whole AP CSA exam? Take the 20-question diagnostic and Lumi will plan the rest.

Take diagnosticarrow_forward Practice all 10.2

Sample questions

5 of 20 — sign in to practice the rest with adaptive difficulty and mastery tracking.

Sample 1difficulty 2/5
```
// mergesort on n elements
```
$What is the time complexity?$
- A
  $O(n)$
- B
  $O(n log n)$
  check_circle
- C
  $O(log n)$
- D
  $O(n^2)$
Why
$Mergesort divides log n levels and merges O(n) per level: O(n log n).$
View full solution & statsarrow_forward
Sample 2difficulty 2/5
```
// binary search on sorted array of size n
```
$What is the worst-case time complexity?$
- A
  $O(n log n)$
- B
  $O(log n)$
  check_circle
- C
  $O(1)$
- D
  $O(n)$
Why
$Binary search halves the search space each step, giving O(log n).$
View full solution & statsarrow_forward
Sample 3difficulty 2/5
```
int[] a = {5, 2, 8, 1, 9};
// attempt binary search on a
```
$Why might binary search fail on this array?$
- A
  $Binary search needs even length$
- B
  $The array is too small$
- C
  $The array is not sorted$
  check_circle
- D
  $Arrays must be Strings$
Why
$Binary search requires the array to be sorted; this array is not.$
View full solution & statsarrow_forward

Sample 4difficulty 3/5

int[] left = {2, 5, 8};
int[] right = {1, 3, 7};
int[] out = new int[6];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
  if (left[i] <= right[j]) out[k++] = left[i++];
  else out[k++] = right[j++];
}
while (i < left.length) out[k++] = left[i++];
while (j < right.length) out[k++] = right[j++];

What is out after merging?

A
${1, 2, 3, 5, 7, 8}$
check_circle
B
${1, 3, 7, 2, 5, 8}$
C
${8, 7, 5, 3, 2, 1}$
D
${2, 5, 8, 1, 3, 7}$

Why

The merge interleaves to produce a fully sorted array.

View full solution & statsarrow_forward

Sample 5difficulty 3/5
```
int[] a = {6, 3, 8, 5, 2, 7, 4, 1};
int mid = a.length / 2;
int[] left = new int[mid];
int[] right = new int[a.length - mid];
for (int i = 0; i < mid; i++) left[i] = a[i];
for (int i = mid; i < a.length; i++) right[i - mid] = a[i];
```
$What is right after the divide step?$
- A
  ${1, 4, 7, 2}$
- B
  ${6, 3, 8, 5}$
- C
  ${6, 3, 8, 5, 2, 7, 4, 1}$
- D
  ${2, 7, 4, 1}$
  check_circle
Why
$The right half of an 8-element array is the second 4 elements.$
View full solution & statsarrow_forward

Predict my AP scorearrow_forward