10.2 Recursion

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? Why? int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};

• 3
• 2
• 4
• 1

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…”

Time for a popcorn hack!

Now let’s see how this code works:

public class MergeSort {

    // Main method to test merge sort
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array:");
        printArray(arr);
    }

    // this is the method to divide and sort the array
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            //  sort the left half
            mergeSort(arr, left, mid);

            //  sort the right half
            mergeSort(arr, mid + 1, right);
            //notice that we are calling the function inside itself, this is recursive sorting
            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    // this is the method to merge two sorted subarrays
    public static void merge(int[] arr, int left, int mid, int right) {
        // Sizes of the two subarrays
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // We are creating the temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Here, we are copying data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }

        // Merge the temporary arrays back into the original array
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArray, if there are any
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArray, if there are  any
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Utility method to print the array
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
MergeSort.main(null);

Original array:
38 27 43 3 9 82 10 

Sorted array:
3 9 10 27 38 43 82