4.17 Recursive searching and sortingBinary search and merge sort

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}
- line 3-4 The search range starts as the whole array
- line 7 Integer division: the middle, rounded down
- line 14 Too small: throw away mid and everything left of it
- line 18 Too big: throw away mid and everything right of it
- line 5-21 When the range is empty, the target is not there
?Wait, why does (low + high) / 2 always give a valid index?
| target | low | high | mid | a[mid] | next |
|---|---|---|---|---|---|
| 47 | 0 | 8 | 4 | 30 | 30 < 47: low = 5 |
| 47 | 5 | 8 | 6 | 47 | found: return 6 |
| 10 | 0 | 8 | 4 | 30 | 30 > 10: high = 3 |
| 10 | 0 | 3 | 1 | 9 | 9 < 10: low = 2 |
| 10 | 2 | 3 | 2 | 15 | 15 > 10: high = 1 |
| 10 | 2 | 1 | low > high: return -1 |
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 elements | linear search, worst case | binary search, worst case |
|---|---|---|
| 8 | 8 checks | 4 checks |
| 16 | 16 checks | 5 checks |
| 100 | 100 checks | 7 checks |
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |
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)
- line 4-7 Base case 1: an empty range, not found
- line 9-12 Base case 2: found it
- line 15-17 Recursive calls on one half of the range
I thought about it. Show me
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.
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}
- line 3 Base case: a range of 0 or 1 element is already sorted
- line 6-7 Sort the left half, then the right half
- line 8 Merge the two sorted halves
- line 20-29 Take the smaller front value of the two halves
- line 32-38 One half ran out: copy the rest of the other
?Wait, why is one element already sorted?
- 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. - 7 vs 19: take 7. 12 vs 19: take 12. 38 vs 19: take 19.
- 38 vs 26: take 26. 38 vs 44: take 38. 50 vs 44: take 44.
- 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
- Only compare the two front values.
- After you take a value, the next one in that half becomes its front.
- When one half runs out, copy the other half's leftovers.
- A30, 47, 53
- B30, 53
- C41, 53
- 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.
- A{2, 5} and {1, 8}
- B{5, 2} and {8, 1}
- C{1, 2} and {5, 8}
- 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.