// 第 2 周 – 在有序数组中二分查找
// 运行：java BinarySearch.java
public class BinarySearch {

    // 迭代的二分查找。返回 x 的下标，找不到时返回 -1。
    //   伪代码（下标从 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 可能溢出！
            if (a[mid] == x) {
                return mid;
            } else if (a[mid] < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    // 同样的算法，打印每一步。
    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;
    }

    // n 个元素时最坏情况下需要多少步？（≈ 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));
        }

        // Java 内置的版本
        System.out.println();
        System.out.println("java.util.Arrays.binarySearch(a, 56) = " + java.util.Arrays.binarySearch(a, 56));
    }
}