Divide and Conquer Explained — Recursion, Real Examples and Pitfalls

public class SumOfArray {

    /**
     * Calculates the sum of all elements in an integer array
     * using the divide and conquer pattern.
     *
     * @param numbers  the array to sum
     * @param left     the starting index of the current sub-array
     * @param right    the ending index of the current sub-array (inclusive)
     * @return         the total sum of elements from left to right
     */
    public static int sumDivideAndConquer(int[] numbers, int left, int right) {

        // CONQUER — base case: a single element is its own sum
        if (left == right) {
            return numbers[left];
        }

        // DIVIDE — find the midpoint to split the array into two halves
        int midpoint = left + (right - left) / 2;
        // Note: we use (right - left) / 2 instead of (left + right) / 2
        // to avoid integer overflow when indices are large.

        // CONQUER — recursively sum the left half
        int leftSum  = sumDivideAndConquer(numbers, left, midpoint);

        // CONQUER — recursively sum the right half
        int rightSum = sumDivideAndConquer(numbers, midpoint + 1, right);

        // COMBINE — add both halves together to get the full sum
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] salesFigures = {120, 340, 85, 210, 430, 95, 275};

        int totalSales = sumDivideAndConquer(salesFigures, 0, salesFigures.length - 1);

        System.out.println("Individual figures: ");
        for (int figure : salesFigures) {
            System.out.print(figure + " ");
        }
        System.out.println();
        System.out.println("Total sum (divide & conquer): " + totalSales);
    }
}

public class RecursiveBinarySearch {

    /**
     * Searches for a target temperature in a sorted array of readings.
     *
     * @param sortedTemps  a sorted array of temperature readings
     * @param left         the left boundary of the current search window
     * @param right        the right boundary of the current search window
     * @param target       the temperature value we're looking for
     * @return             the index of the target, or -1 if not found
     */
    public static int binarySearch(int[] sortedTemps, int left, int right, int target) {

        // CONQUER — base case: search window is empty, target does not exist
        if (left > right) {
            return -1;
        }

        // DIVIDE — find the middle of the current search window
        int midIndex = left + (right - left) / 2;

        // CONQUER — direct hit: target is exactly at the midpoint
        if (sortedTemps[midIndex] == target) {
            return midIndex;
        }

        // CONQUER + DIVIDE — target is smaller, search the LEFT half only
        if (sortedTemps[midIndex] > target) {
            return binarySearch(sortedTemps, left, midIndex - 1, target);
        }

        // CONQUER + DIVIDE — target is larger, search the RIGHT half only
        return binarySearch(sortedTemps, midIndex + 1, right, target);
    }

    public static void main(String[] args) {
        int[] dailyHighTemps = {-5, 2, 8, 14, 19, 23, 27, 31, 36};
        int targetTemp = 23;
        int notPresentTemp = 20;

        int foundIndex = binarySearch(dailyHighTemps, 0, dailyHighTemps.length - 1, targetTemp);
        int missingIndex = binarySearch(dailyHighTemps, 0, dailyHighTemps.length - 1, notPresentTemp);

        System.out.println("Array: [-5, 2, 8, 14, 19, 23, 27, 31, 36]");
        System.out.println("Searching for " + targetTemp + "°C → found at index: " + foundIndex);
        System.out.println("Searching for " + notPresentTemp + "°C → found at index: " + missingIndex + " (not present)");

        // Show how few steps it takes — only log2(9) ≈ 4 comparisons needed
        System.out.println("\nMax comparisons for 9 elements: ~" + (int) Math.ceil(Math.log(dailyHighTemps.length) / Math.log(2)));
    }
}

import java.util.Arrays;

public class MergeSort {

    /**
     * Entry point for merge sort. Sorts the given array in ascending order.
     * This is a classic divide and conquer implementation.
     *
     * @param items  the array of integers to sort (modified in place)
     */
    public static void mergeSort(int[] items) {
        // Base case: an array of 0 or 1 element is already sorted
        if (items.length <= 1) {
            return;
        }

        // DIVIDE — split the array into two roughly equal halves
        int midpoint = items.length / 2;

        // Create separate arrays for each half (uses extra O(n) space)
        int[] leftHalf  = Arrays.copyOfRange(items, 0, midpoint);
        int[] rightHalf = Arrays.copyOfRange(items, midpoint, items.length);

        // CONQUER — recursively sort each half independently
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        // COMBINE — merge the two sorted halves back into the original array
        merge(items, leftHalf, rightHalf);
    }

    /**
     * Merges two sorted arrays (leftHalf and rightHalf) into the destination array.
     * This is the heart of merge sort — the combine step.
     *
     * @param destination  the array to write merged results into
     * @param leftHalf     a sorted sub-array (left portion)
     * @param rightHalf    a sorted sub-array (right portion)
     */
    private static void merge(int[] destination, int[] leftHalf, int[] rightHalf) {
        int leftPointer  = 0; // tracks our position in leftHalf
        int rightPointer = 0; // tracks our position in rightHalf
        int destPointer  = 0; // tracks where we write in destination

        // Walk both halves simultaneously, always picking the smaller front element
        while (leftPointer < leftHalf.length && rightPointer < rightHalf.length) {
            if (leftHalf[leftPointer] <= rightHalf[rightPointer]) {
                // Left element is smaller (or equal — this <= keeps the sort STABLE)
                destination[destPointer] = leftHalf[leftPointer];
                leftPointer++;
            } else {
                // Right element is smaller
                destination[destPointer] = rightHalf[rightPointer];
                rightPointer++;
            }
            destPointer++;
        }

        // Copy any remaining elements from leftHalf (right half is already exhausted)
        while (leftPointer < leftHalf.length) {
            destination[destPointer] = leftHalf[leftPointer];
            leftPointer++;
            destPointer++;
        }

        // Copy any remaining elements from rightHalf (left half is already exhausted)
        while (rightPointer < rightHalf.length) {
            destination[destPointer] = rightHalf[rightPointer];
            rightPointer++;
            destPointer++;
        }
    }

    public static void main(String[] args) {
        int[] examScores = {78, 45, 92, 13, 67, 55, 88, 23, 100, 34};

        System.out.println("Before sorting: " + Arrays.toString(examScores));

        mergeSort(examScores);

        System.out.println("After sorting:  " + Arrays.toString(examScores));

        // Demonstrate with a nearly-sorted array — merge sort handles this consistently
        int[] nearlyOrdered = {1, 2, 4, 3, 5, 6};
        System.out.println("\nNearly sorted before: " + Arrays.toString(nearlyOrdered));
        mergeSort(nearlyOrdered);
        System.out.println("Nearly sorted after:  " + Arrays.toString(nearlyOrdered));
    }
}

/**
 * Finds the maximum subarray sum using divide and conquer.
 * This is a classic interview problem (Kadane's D&C version).
 * Given an array of integers (possibly negative), find the contiguous
 * sub-array that has the largest sum.
 *
 * Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → max sum is 6 (subarray [4,-1,2,1])
 */
public class MaximumSubarraySum {

    public static int findMaxSubarraySum(int[] values, int left, int right) {

        // BASE CASE — a single element: its own sum is the only option
        if (left == right) {
            return values[left];
        }

        // DIVIDE — split into left and right halves
        int midpoint = left + (right - left) / 2;

        // CONQUER — find the max subarray sum entirely in the left half
        int maxLeftSum  = findMaxSubarraySum(values, left, midpoint);

        // CONQUER — find the max subarray sum entirely in the right half
        int maxRightSum = findMaxSubarraySum(values, midpoint + 1, right);

        // COMBINE — find the max subarray sum that CROSSES the midpoint
        // (this is the key insight: a crossing subarray uses elements from BOTH halves)
        int maxCrossingSum = findMaxCrossingSum(values, left, midpoint, right);

        // The answer is the best of all three possibilities
        return Math.max(maxCrossingSum, Math.max(maxLeftSum, maxRightSum));
    }

    /**
     * Finds the maximum sum of a subarray that includes the midpoint element
     * and extends into both the left and right halves.
     */
    private static int findMaxCrossingSum(int[] values, int left, int midpoint, int right) {

        // Extend leftward from midpoint, tracking the best running sum
        int leftRunningSum  = Integer.MIN_VALUE;
        int runningTotal    = 0;
        for (int i = midpoint; i >= left; i--) {
            runningTotal   += values[i];
            leftRunningSum  = Math.max(leftRunningSum, runningTotal);
        }

        // Extend rightward from midpoint+1, tracking the best running sum
        int rightRunningSum = Integer.MIN_VALUE;
        runningTotal        = 0;
        for (int i = midpoint + 1; i <= right; i++) {
            runningTotal    += values[i];
            rightRunningSum  = Math.max(rightRunningSum, runningTotal);
        }

        // The crossing sum is the best left extension + best right extension
        return leftRunningSum + rightRunningSum;
    }

    public static void main(String[] args) {
        int[] portfolioReturns = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int bestGain = findMaxSubarraySum(portfolioReturns, 0, portfolioReturns.length - 1);

        System.out.println("Daily returns: [-2, 1, -3, 4, -1, 2, 1, -5, 4]");
        System.out.println("Best consecutive gain window sum: " + bestGain);
        // Subarray [4, -1, 2, 1] gives sum = 6

        int[] allNegative = {-8, -3, -6, -2, -5};
        int leastBadLoss = findMaxSubarraySum(allNegative, 0, allNegative.length - 1);
        System.out.println("\nAll-negative returns: [-8, -3, -6, -2, -5]");
        System.out.println("Best (least bad) single element: " + leastBadLoss);
    }
}