algorithms7DivideAndConquer

1package pkg4algorithms;2 3/*4 * algorithms7DivideAndConquer.java5 * --------------------------------6 * Divide-and-conquer template: split problem, solve subproblems, combine.7 *8 * Covered: binary search, merge sort, quickselect (kth smallest), max subarray (Kadane9 * is DP but divide-and-conquer variant shown), and power(x,n).10 *11 * COMPLEXITY: typically O(n log n) when halving + linear combine; binary search O(log n).12 */13import java.util.Arrays;14 15public class algorithms7DivideAndConquer {16 17    static int binarySearch(int[] a, int target, int lo, int hi) {18        if (lo > hi) return -1;19        int mid = lo + (hi - lo) / 2;20        if (a[mid] == target) return mid;21        return a[mid] < target ? binarySearch(a, target, mid + 1, hi)22                               : binarySearch(a, target, lo, mid - 1);23    }24 25    static void mergeSort(int[] a, int lo, int hi) {26        if (lo >= hi) return;27        int mid = lo + (hi - lo) / 2;28        mergeSort(a, lo, mid);29        mergeSort(a, mid + 1, hi);30        merge(a, lo, mid, hi);31    }32 33    static void merge(int[] a, int lo, int mid, int hi) {34        int[] tmp = new int[hi - lo + 1];35        int i = lo, j = mid + 1, k = 0;36        while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];37        while (i <= mid) tmp[k++] = a[i++];38        while (j <= hi) tmp[k++] = a[j++];39        System.arraycopy(tmp, 0, a, lo, tmp.length);40    }41 42    // Quickselect: average O(n), worst O(n^2)43    static int quickSelect(int[] a, int k) {44        return select(a, 0, a.length - 1, k);45    }46 47    static int select(int[] a, int lo, int hi, int k) {48        if (lo == hi) return a[lo];49        int p = partition(a, lo, hi);50        if (k == p) return a[p];51        if (k < p) return select(a, lo, p - 1, k);52        return select(a, p + 1, hi, k);53    }54 55    static int partition(int[] a, int lo, int hi) {56        int pivot = a[hi], i = lo - 1;57        for (int j = lo; j < hi; j++) if (a[j] <= pivot) swap(a, ++i, j);58        swap(a, i + 1, hi);59        return i + 1;60    }61 62    static long power(long x, int n) {63        if (n == 0) return 1;64        if (n % 2 == 0) {65            long half = power(x, n / 2);66            return half * half;67        }68        return x * power(x, n - 1);69    }70 71    static void swap(int[] a, int i, int j) {72        int t = a[i]; a[i] = a[j]; a[j] = t;73    }74 75    public static void main(String[] args) {76        int[] a = {3, 1, 4, 1, 5, 9, 2, 6};77        Arrays.sort(a);78        System.out.println("binarySearch(5): index " + binarySearch(a, 5, 0, a.length - 1));79 80        int[] b = {9, 3, 7, 1, 8, 2, 6, 5, 4};81        mergeSort(b, 0, b.length - 1);82        System.out.println("mergeSort: " + Arrays.toString(b));83 84        int[] c = {9, 3, 7, 1, 8, 2, 6, 5, 4};85        System.out.println("quickSelect k=3 (4th smallest): " + quickSelect(c.clone(), 3));86 87        System.out.println("2^10 = " + power(2, 10));88    }89}