九章模板

    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) { //可以把这个条件和第三个条件合并，因为结果一样
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
                // or start = mid + 1 这种加1或者减1的写法就不是模板了，不推荐。
            } else {
                end = mid;
                // or end = mid - 1
            }
        }

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

改进后的九章模板

模板的精髓在于通过二分，筛选出两个候选数（其余数肯定不符合条件），然后分别检查这两个候选数。
优点：通用，避免死循环、corner case

    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) { //target在右半边
                start = mid;
            } else { //target在左半边
                end = mid; //将原来的第一个和第三个条件合并。
            }
        }

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

Counting Sort

    /**
     * A: input array B: output array C: count array
     * O(n + k); O(n + k)
     * 定新数组大小——找出待排序的数组中最大和最小的元素
     统计次数——统计数组中每个值为i的元素出现的次数，存入新数组C的第i项
     对统计次数逐个累加——对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
     反向填充目标数组——将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
     其中反向填充主要是为了避免重复元素落入新数组的同一索引处。
     https://algorithm.yuanbin.me/zh-hans/basics_sorting/counting_sort.html
     */
    public static int[] countingSort(int[] A) {
        int[] B = new int[A.length]; //保存结果
        // 假设A中的数据a'有，0<=a' && a' < k并且k=100
        int k = 10;
        int[] C = new int[k];
        // 计数
        for (int j = 0; j < A.length; j++) { //O(n)
            int a = A[j];
            C[a] += 1;
        }
        System.out.println(Arrays.toString(C));
        // 求计数和
        for (int i = 1; i < k; i++) { //O(k)
            C[i] = C[i] + C[i - 1];
        }
        System.out.println(Arrays.toString(C));
        // 整理
        for (int j = A.length - 1; j >= 0; j--) { //反向填充目标数组
            int a = A[j];
            B[C[a] - 1] = a;
            C[a]--;
            System.out.println(Arrays.toString(B));
        }
        return B;
    }

    public static void main(String[] argv) {
        int[] A = CountingSort.countingSort(new int[]{9, 3, 2, 8, 1});
        System.out.println(Arrays.toString(A));
    }