AP Computer Science A · Unit 4 lecture · Part 13 of 14 · 11 min

4.17 Recursive searching and sortingBinary search and merge sort

Mr. Thompkins
Guess my number between 1 and 100. You'd never guess 1, then 2, then 3. You'd guess 50, and I'd say "higher", and half the numbers would vanish in one guess. That's binary search.

Binary search only works on sorted data. It keeps a range, from low to high, where the target could still be. Each step looks at the middle element. If it's the target, done. If the middle is too small, the target can only be to its right, so low becomes mid + 1. If it's too big, high becomes mid - 1. When low passes high, the range is empty and the target isn't there.

1public static int binarySearch(int[] a, int target)2{3    int low = 0;14    int high = a.length - 1;15    while (low <= high)56    {7        int mid = (low + high) / 2;28        if (a[mid] == target)9        {10            return mid;11        }12        else if (a[mid] < target)13        {14            low = mid + 1;315        }16        else17        {18            high = mid - 1;419        }20    }21    return -1;522}
  1. line 3-4 The search range starts as the whole array
  2. line 7 Integer division: the middle, rounded down
  3. line 14 Too small: throw away mid and everything left of it
  4. line 18 Too big: throw away mid and everything right of it
  5. line 5-21 When the range is empty, the target is not there
Binary search with a loop.
?Wait, why does (low + high) / 2 always give a valid index?
low and high are ints, so the division is integer division and rounds down to a whole number between low and high. For low 5 and high 8, (5 + 8) / 2 is 13 / 2, which is 6.
targetlowhighmida[mid]next
470843030 < 47: low = 5
4758647found: return 6
100843030 > 10: high = 3
1003199 < 10: low = 2
102321515 > 10: high = 1
1021low > high: return -1
Searching {4, 9, 15, 22, 30, 41, 47, 53, 68} for 47 (found in 2 steps) and for 10 (not there, 3 steps).

Each step throws away about half of what's left, so even a huge sorted array takes only a few steps. Linear search might have to check every element. That's why binary search is usually much faster, but only when the data is sorted.

sorted elementslinear search, worst casebinary search, worst case
88 checks4 checks
1616 checks5 checks
100100 checks7 checks
1,0001,000 checks10 checks
1,000,0001,000,000 checks20 checks
The most elements each search might have to check.

Binary search is naturally recursive, because the smaller job is the same job: search one half. The recursive version passes the range as parameters and has two base cases, an empty range and a found target.

1public static int search(int[] a, int target,2                         int low, int high)3{4    if (low > high)15    {16        return -1;17    }18    int mid = (low + high) / 2;9    if (a[mid] == target)210    {211        return mid;212    }213    if (a[mid] < target)14    {15        return search(a, target, mid + 1, high);316    }17    return search(a, target, low, mid - 1);318}19// first call: search(a, 47, 0, a.length - 1)
  1. line 4-7 Base case 1: an empty range, not found
  2. line 9-12 Base case 2: found it
  3. line 15-17 Recursive calls on one half of the range
output › 6
The same search, written recursively.
Pause and think
What does binarySearch return for the unsorted array {7, 2, 9, 1, 5} with target 1?
I thought about it. Show me
-1, even though 1 is at index 3. mid is 2, and 9 > 1, so high becomes 1. Then mid is 0, and 7 > 1, so high becomes -1 and the range is empty. On unsorted data the "throw away half" step throws away the answer.

Merge sort

Merge sort uses the same divide-and-conquer idea to sort. Split the array in half, sort each half (recursively, by splitting again), then merge the two sorted halves into one sorted whole. The base case is a piece of one element, which is already sorted. Merging is the easy part: repeatedly take the smaller of the two front values.

38 12 50 7 26 44 3 1938 12 50 726 44 3 1938 1250 726 443 193812507264431912 387 5026 443 197 12 38 503 19 26 443 7 12 19 26 38 44 50
Merge sort on 8 values. Blue rows split, purple is the base case, green rows merge.
1public static void mergeSort(int[] a, int lo, int hi)2{3    if (lo < hi)14    {5        int mid = (lo + hi) / 2;6        mergeSort(a, lo, mid);27        mergeSort(a, mid + 1, hi);28        merge(a, lo, mid, hi);39    }10}1112public static void merge(int[] a, int lo, int mid, int hi)13{14    int[] temp = new int[hi - lo + 1];15    int i = lo;16    int j = mid + 1;17    int k = 0;18    while (i <= mid && j <= hi)19    {20        if (a[i] <= a[j])421        {422            temp[k] = a[i];423            i++;424        }425        else426        {427            temp[k] = a[j];428            j++;429        }430        k++;31    }32    while (i <= mid)533    {34        temp[k] = a[i];35        i++;36        k++;37    }38    while (j <= hi)539    {40        temp[k] = a[j];41        j++;42        k++;43    }44    for (k = 0; k < temp.length; k++)45    {46        a[lo + k] = temp[k];47    }48}
  1. line 3 Base case: a range of 0 or 1 element is already sorted
  2. line 6-7 Sort the left half, then the right half
  3. line 8 Merge the two sorted halves
  4. line 20-29 Take the smaller front value of the two halves
  5. line 32-38 One half ran out: copy the rest of the other
output › mergeSort({38, 12, 50, 7, 26, 44, 3, 19}, 0, 7) gives 3 7 12 19 26 38 44 50
Merge sort and its merge helper. You trace this on the exam; you won't write it.
?Wait, why is one element already sorted?
There's nothing to compare it with, so it can't be out of order. That's why the recursion can stop there: when lo is not less than hi, the range has at most one element, and mergeSort does nothing.
Merge two halves
The two sorted halves {7, 12, 38, 50} and {3, 19, 26, 44} are merged. List the values in the order they go into the result.
  1. Compare the fronts: 7 and 3. Take 3.
    Why?
    Both halves are sorted, so the smallest remaining value is always at one of the two fronts.
  2. 7 vs 19: take 7. 12 vs 19: take 12. 38 vs 19: take 19.
  3. 38 vs 26: take 26. 38 vs 44: take 38. 50 vs 44: take 44.
  4. The right half is used up, so copy the rest of the left half: 50.

Answer: 3, 7, 12, 19, 26, 38, 44, 50

Stuck? Get a hint
  1. Only compare the two front values.
  2. After you take a value, the next one in that half becomes its front.
  3. When one half runs out, copy the other half's leftovers.
Check yourself
Binary search (the loop version above) looks for 53 in {4, 9, 15, 22, 30, 41, 47, 53, 68}. Which values of a[mid] does it check, in order?
  1. A30, 47, 53
  2. B30, 53
  3. C41, 53
  4. D30, 41, 47, 53
Show the answer

A. low 0, high 8: mid 4 is 30, too small, so low is 5. mid (5 + 8) / 2 = 6 is 47, too small, so low is 7. mid (7 + 8) / 2 = 7 is 53: found. The last choice is the trap: binary search jumps over 41; it never steps one element at a time.

Check yourself
Merge sort sorts {5, 2, 8, 1}. Just before the final merge, what are the two sorted halves?
  1. A{2, 5} and {1, 8}
  2. B{5, 2} and {8, 1}
  3. C{1, 2} and {5, 8}
  4. D{2, 8} and {1, 5}
Show the answer

A. Merge sort splits by position: {5, 2} and {8, 1}. Each half is sorted on its own, giving {2, 5} and {1, 8}, and the final merge makes {1, 2, 5, 8}. The second choice is the halves before sorting. The third mixes values between halves, which the split never does.

  • Binary search needs sorted data. Check the middle, discard half, repeat until found or low > high.
  • Binary search takes about log2(n) steps: 10 for 1,000 elements, 20 for a million.
  • Merge sort: split in half, sort each half recursively, merge. One element is the base case.
  • Merging takes the smaller front value each time, then copies whatever is left.