Merge Sort Hack # 1

  • Use the integer mergesort that we created and adapt it to sort an array of Java String objects. We recommend using the compareTo() method of the String class for this.
import java.util.Arrays;

public class Merge{
   
    public static void mergeSort(String[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        String[] left = new String[mid];
        String[] right = new String[arr.length - mid];
        System.arraycopy(arr, 0, left, 0, left.length);
        System.arraycopy(arr, mid, right, 0, right.length);
        mergeSort(left);
        mergeSort(right);
        merge(left, right, arr);
    }
    
    private static void merge(String[] left, String[] right, String[] arr) {
        int leftIndex = 0, rightIndex = 0, arrIndex = 0;
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex].compareTo(right[rightIndex]) < 0) {
                arr[arrIndex++] = left[leftIndex++];
            } else {
                arr[arrIndex++] = right[rightIndex++];
            }
        }
        while (leftIndex < left.length) {
            arr[arrIndex++] = left[leftIndex++];
        }
        while (rightIndex < right.length) {
            arr[arrIndex++] = right[rightIndex++];
        }
    }

    public static void main(String[] args) {
        String[] arr = {"banana", "apple", "orange", "pear", "grape"};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

Merge.main(null);

Before sorting: [banana, apple, orange, pear, grape]
After sorting: [apple, banana, grape, orange, pear]

Binary Search Hack # 1

  • Given an int array[] = {1, 3, 5, 7, 9, 23, 45, 67}, search the number 45 and give it's index with Binary search, BUT do this using recursion. Make sure to include informative comments to explain the code as you write the algorithm.
public class BinarySearchRecursive {
    
    /**
     * Recursive binary search method to find the index of a target number in an array
     *
     * @param arr the int array to search
     * @param target the number to search for
     * @param low the lower index of the search range
     * @param high the upper index of the search range
     * @return the index of the target number in the array, or -1 if not found
     */
    public static int binarySearch(int[] arr, int target, int low, int high) {
        // base case: search range is empty
        if (low > high) {
            return -1;
        }
        
        // calculate the middle index of the search range
        int mid = (low + high) / 2;
        
        // check if the middle element is the target
        if (arr[mid] == target) {
            return mid;
        }
        
        // recursively search the left or right half of the array based on the target value
        if (target < arr[mid]) {
            return binarySearch(arr, target, low, mid - 1);
        } else {
            return binarySearch(arr, target, mid + 1, high);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 23, 45, 67};
        int target = 45;
        int low = 0;
        int high = arr.length - 1;
        
        // call the recursive binary search method
        int index = binarySearch(arr, target, low, high);
        
        // print the result
        if (index != -1) {
            System.out.println("The target number " + target + " is found at index " + index + ".");
        } else {
            System.out.println("The target number " + target + " is not found in the array.");
        }
    }
}

BinarySearchRecursive.main(null);

The target number 45 is found at index 6.

Binary Search Hack #2 EC

  • Given an unsorted array of int[] array = {5, 6, 3, 1, 8, 9, 4, 7, 2}, use merge sort as taught previously and combine learning with this lesson to implement a binary search to find index of the number 7.
import java.util.Arrays;

public class MergeSortBinarySearch {
    
    /**
     * Merge sort method to sort an int array
     *
     * @param arr the int array to sort
     */
    public static void mergeSort(int[] arr) {
        // base case: array has 1 or 0 elements
        if (arr.length <= 1) {
            return;
        }
        
        // divide the array into two halves
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        
        // recursively sort each half
        mergeSort(left);
        mergeSort(right);
        
        // merge the two sorted halves
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    
    /**
     * Binary search method to find the index of a target number in a sorted array
     *
     * @param arr the sorted int array to search
     * @param target the number to search for
     * @param low the lower index of the search range
     * @param high the upper index of the search range
     * @return the index of the target number in the array, or -1 if not found
     */
    public static int binarySearch(int[] arr, int newTarget, int low, int high) {
        // base case: search range is empty
        if (low > high) {
            return -1;
        }
        
        // calculate the middle index of the search range
        int mid = (low + high) / 2;
        
        // check if the middle element is the target
        if (arr[mid] == newTarget) {
            return mid;
        }
        
        // recursively search the left or right half of the array based on the target value
        if (newTarget < arr[mid]) {
            return binarySearch(arr, newTarget, low, mid - 1);
        } else {
            return binarySearch(arr, newTarget, mid + 1, high);
        }
    }
    
    public static void main(String[] args) {
        int[] array = {5, 6, 3, 1, 8, 9, 4, 7, 2};
        
        // sort the array using merge sort
        mergeSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
        
        // find the index of the number 7 using binary search
        int newTarget = 7;
        int low = 0;
        int high = array.length - 1;
        int index = binarySearch(array, newTarget, low, high);
        
        // print the result
        if (index != -1) {
            System.out.println("The target number " + newTarget + " is found at index " + index + ".");
        } else {
            System.out.println("The target number " + newTarget + " is not found in the array.");
        }
    }
}

MergeSortBinarySearch.main(null);

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
The target number 7 is found at index 6.