ACSA Exam Prep
Unit 4 · Data Collections · Topic 4.17

Recursive Searching and Sorting

Skill 4.ASkill 4.B

Big idea: Binary search and merge sort both split the data in half. Binary search throws half away each step; merge sort sorts both halves and merges them.

Learning objectives
  • Determine the result of executing recursive algorithms that use strings or collections.
  • Determine the result of each iteration of a binary search algorithm used to search for information in a collection.
  • Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

Binary search

Binary search only works on sorted data. Check the middle element; if it isn't the target, keep only the half that could contain it.

Methods
static int search(int[] a, int target) {
  int lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    System.out.println("check index " + mid + " (" + a[mid] + ")");
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
Using them
int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
System.out.println(search(a, 23));
Output
check index 4 (16)
check index 7 (56)
check index 5 (23)
5

How fast is it?

Each check halves what's left, so n items take about log₂(n) checks. 1,000 items take about 10; 1,000,000 take about 20. Linear search on the same data could take 1,000,000.

Merge sort

Split the list in half, recursively sort each half, then merge the two sorted halves by repeatedly taking the smaller front element.

Methods
static void mergeSort(int[] a, int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  mergeSort(a, lo, mid);
  mergeSort(a, mid + 1, hi);
  int[] temp = new int[hi - lo + 1];
  int i = lo, j = mid + 1, k = 0;
  while (i <= mid || j <= hi) {
    if (j > hi || (i <= mid && a[i] <= a[j])) {
      temp[k] = a[i];
      i++;
    } else {
      temp[k] = a[j];
      j++;
    }
    k++;
  }
  for (k = 0; k < temp.length; k++) a[lo + k] = temp[k];
}
Using them
int[] a = {38, 27, 43, 3, 9, 82, 10};
mergeSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
Output
[3, 9, 10, 27, 38, 43, 82]

Merge sort, step by step

StepState
Split[38, 27, 43, 3] [9, 82, 10]
Split again[38, 27] [43, 3] [9, 82] [10]
Down to singles[38] [27] [43] [3] [9] [82] [10]
Merge pairs[27, 38] [3, 43] [9, 82] [10]
Merge[3, 27, 38, 43] [9, 10, 82]
Final merge[3, 9, 10, 27, 38, 43, 82]
Key points
  • Recursion can traverse Strings, arrays, and ArrayLists.
  • Binary search needs sorted data, checks the middle, and discards half each step.
  • Binary search is usually much faster than linear search.
  • Merge sort: split in half, sort each half recursively, merge the sorted halves.
Watch out
  • Binary search on unsorted data gives wrong answers.
  • With integer division, mid = (lo + hi) / 2 rounds down.
Exam tip
  • For "which elements are checked" questions, keep lo, hi, and mid in a little table.
Quick check
Binary search for 8 in {1, 3, 5, 7, 8, 10, 12}: which values are checked?
Show answer
7 (index 3), then 10 (index 5), then 8 (index 4).
Not on the exam
  • Search algorithms other than linear and binary.
  • Sorts other than selection, insertion, and merge sort.
Practice 4.17 (12 questions)