algorithms2SearchingAlgorithms

1package pkg4algorithms;2 3/*4 * algorithms2SearchingAlgorithms.java5 * ------------------------6 * Linear search, binary search (iterative + recursive), and two classic7 * "binary search on answer" variants: first/last occurrence.8 *9 * COMPLEXITY: linear O(n); binary O(log n) but requires a SORTED array.10 */11import java.util.Arrays;12 13public class algorithms2SearchingAlgorithms {14 15    static int linear(int[] a, int target) {16        for (int i = 0; i < a.length; i++) if (a[i] == target) return i;17        return -1;18    }19 20    static int binary(int[] a, int target) {21        int lo = 0, hi = a.length - 1;22        while (lo <= hi) {23            int mid = lo + (hi - lo) / 2;     // avoids overflow vs (lo+hi)/224            if (a[mid] == target) return mid;25            if (a[mid] < target) lo = mid + 1;26            else hi = mid - 1;27        }28        return -1;29    }30 31    static int binaryRecursive(int[] a, int target, int lo, int hi) {32        if (lo > hi) return -1;33        int mid = lo + (hi - lo) / 2;34        if (a[mid] == target) return mid;35        return a[mid] < target ? binaryRecursive(a, target, mid + 1, hi)36                               : binaryRecursive(a, target, lo, mid - 1);37    }38 39    // First index where a[i] == target (handles duplicates)40    static int firstOccurrence(int[] a, int target) {41        int lo = 0, hi = a.length - 1, res = -1;42        while (lo <= hi) {43            int mid = lo + (hi - lo) / 2;44            if (a[mid] == target) { res = mid; hi = mid - 1; }   // keep searching left45            else if (a[mid] < target) lo = mid + 1;46            else hi = mid - 1;47        }48        return res;49    }50 51    static int lastOccurrence(int[] a, int target) {52        int lo = 0, hi = a.length - 1, res = -1;53        while (lo <= hi) {54            int mid = lo + (hi - lo) / 2;55            if (a[mid] == target) { res = mid; lo = mid + 1; }   // keep searching right56            else if (a[mid] < target) lo = mid + 1;57            else hi = mid - 1;58        }59        return res;60    }61 62    public static void main(String[] args) {63        int[] a = {1, 3, 3, 3, 5, 7, 9, 11};64        System.out.println("array: " + Arrays.toString(a));65        System.out.println("linear find 7: index " + linear(a, 7));66        System.out.println("binary find 9: index " + binary(a, 9));67        System.out.println("recursive find 1: index " + binaryRecursive(a, 1, 0, a.length - 1));68        System.out.println("find 13 (absent): " + binary(a, 13));69        System.out.println("first occ of 3: " + firstOccurrence(a, 3));70        System.out.println("last occ of 3:  " + lastOccurrence(a, 3));71    }72}