Divide and Conquer — (low+high)/2 Overflow Fix

package io.thecodeforge.algorithms;

public class SumOfArray {

    /**
     * Calculates the sum of all elements in an integer array
     * using the divide and conquer pattern.
     *
     * This is intentionally a simple example — summing an array
     * doesn't need D&C in practice (a plain loop is faster and clearer).
     * The point here is to see the three-step structure in its purest form
     * before we apply it to harder problems.
     *
     * @param numbers  the array to sum
     * @param left     the starting index of the current sub-array (inclusive)
     * @param right    the ending index of the current sub-array (inclusive)
     * @return         the total sum of elements from index left to right
     */
    public static int sumDivideAndConquer(int[] numbers, int left, int right) {

        // CONQUER — base case: a sub-array of exactly one element.
        // Its sum is itself. No further splitting needed.
        // This is the anchor that stops infinite recursion.
        if (left == right) {
            return numbers[left];
        }

        // DIVIDE — find the midpoint to split into two halves.
        // We use left + (right - left) / 2 instead of (left + right) / 2
        // to prevent integer overflow when indices are large.
        // This formula is equivalent mathematically but safe in 32-bit arithmetic.
        int midpoint = left + (right - left) / 2;

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

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

        // COMBINE — add both halves together.
        // This is the simplest possible combine step: just addition.
        // In merge sort this step is far more involved.
        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 and conquer): " + totalSales);
        System.out.println("Verification (plain sum):       "
            + (120 + 340 + 85 + 210 + 430 + 95 + 275));
    }
}

package io.thecodeforge.algorithms;

public class RecursiveBinarySearch {

    /**
     * Searches for a target temperature in a sorted array of readings.
     * The array MUST be sorted in ascending order before calling this method.
     * Binary search on an unsorted array produces undefined results — no error,
     * just a confidently wrong answer. This is worth repeating.
     *
     * @param sortedTemps  a sorted array of integer temperature readings
     * @param left         the left boundary of the current search window (inclusive)
     * @param right        the right boundary of the current search window (inclusive)
     * @param target       the temperature value we are looking for
     * @return             the index of the target, or -1 if not present
     */
    public static int binarySearch(int[] sortedTemps, int left, int right, int target) {

        // CONQUER — base case: the search window has collapsed to nothing.
        // left > right means we have eliminated all candidates without finding the target.
        if (left > right) {
            return -1;
        }

        // DIVIDE — find the middle index of the current search window.
        // Always use left + (right - left) / 2, never (left + right) / 2.
        // See the production incident in this article for why this matters.
        int midIndex = left + (right - left) / 2;

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

        // CONQUER + DIVIDE — target is smaller than midpoint value.
        // The target must be in the left half if it exists at all.
        // We discard the entire right half and recurse on [left, midIndex-1].
        if (sortedTemps[midIndex] > target) {
            return binarySearch(sortedTemps, left, midIndex - 1, target);
        }

        // CONQUER + DIVIDE — target is larger than midpoint value.
        // The target must be in the right half if it exists at all.
        // We discard the entire left half and recurse on [midIndex+1, right].
        return binarySearch(sortedTemps, midIndex + 1, right, target);

        // Note: there is no combine step here.
        // The answer comes from exactly one recursive call, not from merging two.
        // This is why binary search is described as 'decrease and conquer'.
    }

    public static void main(String[] args) {
        // Array must be sorted — binary search assumes this as a precondition.
        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 + "\u00b0C \u2192 found at index: " + foundIndex);
        System.out.println("Searching for " + notPresentTemp + "\u00b0C \u2192 result: " + missingIndex + " (not present)");

        // Demonstrate the logarithmic depth: log2(9) is approximately 3.17,
        // so at most 4 comparisons are needed for any search on this 9-element array.
        System.out.println("\nMax comparisons for 9 elements: ~"
            + (int) Math.ceil(Math.log(dailyHighTemps.length) / Math.log(2)));
        System.out.println("Max comparisons for 1,000,000 elements: ~"
            + (int) Math.ceil(Math.log(1_000_000) / Math.log(2)));
    }
}

package io.thecodeforge.algorithms;

import java.util.Arrays;

public class MergeSort {

    /**
     * Entry point for merge sort. Sorts the given integer array in ascending order.
     * This is a classic D&C implementation — clear structure over micro-optimisation.
     *
     * Time complexity:  O(n log n) — guaranteed, no bad cases unlike quicksort
     * Space complexity: O(n) — extra memory for the left and right sub-arrays
     * Stability:        Yes — equal elements preserve their original relative order
     *
     * @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 elements is already sorted by definition.
        // This is the anchor. Without it, the recursion never terminates.
        if (items.length <= 1) {
            return;
        }

        // DIVIDE — split into two roughly equal halves.
        // For an array of length 6: midpoint = 3, left = [0..2], right = [3..5].
        int midpoint = items.length / 2;

        // Arrays.copyOfRange creates a new array containing just the specified range.
        // This allocates O(n) extra memory — see the production insight below.
        int[] leftHalf  = Arrays.copyOfRange(items, 0, midpoint);
        int[] rightHalf = Arrays.copyOfRange(items, midpoint, items.length);

        // CONQUER — recursively sort each half independently.
        // These two calls are completely independent of each other.
        // That independence is what makes this D&C rather than DP.
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        // COMBINE — merge the two now-sorted halves back into the original array.
        // All the sorting intelligence lives in merge(), not in the recursive calls above.
        merge(items, leftHalf, rightHalf);
    }

    /**
     * Merges two sorted arrays (leftHalf and rightHalf) into the destination array.
     * This is the heart of merge sort — study this method until you can write it
     * from memory, because interviewers will ask you to.
     *
     * The two-pointer technique: walk both input arrays simultaneously,
     * always writing the smaller of the two current front elements to the destination.
     * When one input is exhausted, copy whatever remains from the other.
     *
     * @param destination  the array to write merged results into
     * @param leftHalf     a fully sorted sub-array (left portion)
     * @param rightHalf    a fully sorted sub-array (right portion)
     */
    private static void merge(int[] destination, int[] leftHalf, int[] rightHalf) {
        int leftPointer  = 0; // current read position in leftHalf
        int rightPointer = 0; // current read position in rightHalf
        int destPointer  = 0; // current write position in destination

        // Main merge loop — runs until one of the two input arrays is exhausted.
        while (leftPointer < leftHalf.length && rightPointer < rightHalf.length) {

            // The <= here (rather than <) is what makes merge sort STABLE.
            // When elements are equal, we take from the left half first,
            // preserving the original relative order of equal elements.
            if (leftHalf[leftPointer] <= rightHalf[rightPointer]) {
                destination[destPointer] = leftHalf[leftPointer];
                leftPointer++;
            } else {
                destination[destPointer] = rightHalf[rightPointer];
                rightPointer++;
            }
            destPointer++;
        }

        // Drain remaining elements from leftHalf.
        // At most one of these two drain loops will execute — the other input
        // was already fully consumed in the main loop above.
        while (leftPointer < leftHalf.length) {
            destination[destPointer] = leftHalf[leftPointer];
            leftPointer++;
            destPointer++;
        }

        // Drain remaining elements from rightHalf.
        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));

        // Merge sort handles already-sorted and reverse-sorted arrays
        // in the same O(n log n) time — no worst-case degradation unlike quicksort.
        int[] reverseOrdered = {9, 7, 5, 3, 1};
        System.out.println("\nReverse ordered before: " + Arrays.toString(reverseOrdered));
        mergeSort(reverseOrdered);
        System.out.println("Reverse ordered after:  " + Arrays.toString(reverseOrdered));

        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));
    }
}

package io.thecodeforge.algorithms;

/**
 * Finds the contiguous sub-array with the maximum sum using divide and conquer.
 * This is a classic problem known as the Maximum Subarray Problem.
 *
 * Given an integer array (possibly with negative values), find the contiguous
 * sub-array that produces the largest sum.
 *
 * Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 *          The maximum subarray is [4, -1, 2, 1] with sum = 6.
 *
 * Time complexity: O(n log n) — the D&C approach.
 * Note: Kadane's algorithm solves this in O(n) with a linear scan,
 * which is better in practice. This D&C version is presented because
 * it is a textbook example of the three-step pattern including a
 * non-trivial combine step, and it appears frequently in interviews.
 */
public class MaximumSubarraySum {

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

        // BASE CASE — a single element: the only possible subarray is itself.
        // Even if it is negative, it is the best (and only) option for this sub-problem.
        if (left == right) {
            return values[left];
        }

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

        // CONQUER — the maximum subarray in the full range is one of three things:
        // 1. Entirely within the left half
        int maxLeftSum  = findMaxSubarraySum(values, left, midpoint);

        // 2. Entirely within the right half
        int maxRightSum = findMaxSubarraySum(values, midpoint + 1, right);

        // 3. Crossing the midpoint — starts somewhere in the left half and
        //    ends somewhere in the right half
        // This third case is the key insight that makes D&C work here.
        // A crossing subarray cannot be found by either recursive call alone.
        int maxCrossingSum = findMaxCrossingSum(values, left, midpoint, right);

        // COMBINE — the answer for this range is the best of all three options.
        return Math.max(maxCrossingSum, Math.max(maxLeftSum, maxRightSum));
    }

    /**
     * Finds the maximum sum of any subarray that crosses the midpoint.
     * Such a subarray must include values[midpoint] and values[midpoint+1].
     * We extend as far left and as far right as the running sum allows.
     */
    private static int findMaxCrossingSum(int[] values, int left, int midpoint, int right) {

        // Extend leftward from the midpoint, accumulating the best possible left extension.
        // We scan right-to-left from midpoint to left.
        int leftRunningSum = Integer.MIN_VALUE;
        int runningTotal   = 0;
        for (int i = midpoint; i >= left; i--) {
            runningTotal  += values[i];
            if (runningTotal > leftRunningSum) {
                leftRunningSum = runningTotal;
            }
        }

        // Extend rightward from midpoint+1, accumulating the best possible right extension.
        int rightRunningSum = Integer.MIN_VALUE;
        runningTotal        = 0;
        for (int i = midpoint + 1; i <= right; i++) {
            runningTotal   += values[i];
            if (runningTotal > rightRunningSum) {
                rightRunningSum = runningTotal;
            }
        }

        // The crossing sum is the best left extension plus the best right extension.
        // Both halves must be included because the crossing subarray spans the midpoint.
        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);
        System.out.println("(Subarray [4, -1, 2, 1] gives sum = 6)");

        // The all-negative case is important: the algorithm should still return
        // the least-negative single element, not zero or Integer.MIN_VALUE.
        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) element: " + leastBadLoss);
        System.out.println("(Correctly returns -2, not 0 or Integer.MIN_VALUE)");
    }
}