Recursion Teach 10.2

10.2 - Recursive Binary Search

What is a binary search?

• highly efficient algorithm used to find a specific target value within a sorted array by repeatedly dividing the search space in half
• it eliminates half of the possible locations with each comparison until the target is found or the search space is exhausted

target = 24
int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

How many iterations do you need to find the target using linear search?

How many calls will be needed to find the target using binary search? (we’ll come back to this)

We know how to find the target iteratively…

• first we pass an array, high & low position (sort of like boundaries for our search), and the target value
• as long as our low position is less than or equal to high position, we can find the middle
• whatever the middle is, we compare it to the target, and adjust our boundaries based off of that comparison
• if the middle value is less than the target, we adjust the low position up
• if the middle value is greater than the target, we adjust the high positiion down
• if the middle value is the target, we return it!

But how do we find it recursively? (Questions below)

Back to our question, how many recursive calls would it take to find the target? (and why?) A. 3 B. 2 C. 1 D. 5

target = 24 int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

recBinarySearch(intArray, 0, 20, 24)
target = 24
int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

recBinarySearch(intArray, 11, 20, 24)
target = 24
int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

recBinarySearch(intArray, 11, 14, 24)
target = 24
int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

Merge Sort: Merge Sort is a more advanced algorithm. It uses a strategy called divide-and-conquer. That means it breaks a big problem into smaller problems, solves those, and then combines the results. Think about sorting a messy pile of papers: you might divide it into smaller piles, organize each one, and then combine them back in order.

How does it work?

A simple way to think about this is with the mantra “left, right, merge… left, right merge… left, right, merge…”

Now let’s take a look at how the code for this works in Java:

This is the splitting of array


public static void mergeSort(int[] array) {
    if (array.length < 2) { // Base case: if the array has one or zero elements
        return;
    }
    int mid = array.length / 2;

    // Split the array into two halves
    int[] left = new int[mid];
    int[] right = new int[array.length - mid];

    for (int i = 0; i < mid; i++) {
        left[i] = array[i];
    }
    for (int i = mid; i < array.length; i++) {
        right[i - mid] = array[i];
    }

    // Recursively sort each half
    mergeSort(left);
    mergeSort(right);

    // Merge the sorted halves
    merge(array, left, right);
}

This is the merge sort algorithm:

public static void merge(int[] array, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;

    // Compare elements from both arrays and copy the smaller one
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            array[k++] = left[i++];
        } else {
            array[k++] = right[j++];
        }
    }

    // Copy any remaining elements from the left array
    while (i < left.length) {
        array[k++] = left[i++];
    }

    // Copy any remaining elements from the right array
    while (j < right.length) {
        array[k++] = right[j++];
    }
}