// Week 2 – Binary search in a sorted array
// Run: java BinarySearch.java
public class BinarySearch {

    // Iterative binary search. Returns the index of x, or -1.
    //   Pseudocode (indexing from 1):
    //     lo ← 1 ; hi ← n
    //     While lo ≤ hi
    //       k ← (lo + hi) div 2
    //       If A[k] = x then Return k
    //       else if A[k] < x then lo ← k + 1
    //       else hi ← k − 1
    //     End while
    //     Return 0
    static int binarySearch(int[] a, int x) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 may overflow for large indexes!
            if (a[mid] == x) {
                return mid;
            } else if (a[mid] < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    // The same, printing the steps.
    static int binarySearchTrace(int[] a, int x) {
        int lo = 0, hi = a.length - 1, step = 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            System.out.printf("  step %d: lo=%d hi=%d mid=%d a[mid]=%d%n", step++, lo, hi, mid, a[mid]);
            if (a[mid] == x) return mid;
            if (a[mid] < x) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    // How many steps are needed in the worst case for n elements? (≈ log2 n + 1)
    static int worstCaseSteps(int n) {
        int steps = 0;
        while (n > 0) {
            n = n / 2;
            steps++;
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] a = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
        System.out.println("Searching for 23");
        System.out.println("  result: index " + binarySearchTrace(a, 23));
        System.out.println("Searching for 40");
        System.out.println("  result: index " + binarySearchTrace(a, 40));

        System.out.println();
        System.out.println("Number of steps in the worst case:");
        System.out.println("             n         linear    binary");
        for (int n : new int[] { 10, 100, 1_000, 1_000_000, 1_000_000_000 }) {
            System.out.printf("%,14d %,14d %9d%n", n, n, worstCaseSteps(n));
        }

        // The built-in Java version
        System.out.println();
        System.out.println("java.util.Arrays.binarySearch(a, 56) = " + java.util.Arrays.binarySearch(a, 56));
    }
}