public static <E extends Comparable<E>> int search(E[] arr, E target) {
        return search(arr, 0, arr.length - 1, target);
    }
    private static <E extends Comparable<E>> int search(E[] arr, int l, int r, E target) {
        if(l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if(arr[mid].compareTo(target) == 0) { // 刚好找到中间的位置
            return mid;
        }else if (arr[mid].compareTo(target) > 0) { // 查找mid前面的元素
            return search(arr, l, mid - 1, target);
        }else { //(arr[mid].compareTo(target) < 0)
            return search(arr, mid + 1, r, target);
        }
    }

private static <E extends Comparable<E>> int search1(E[] arr, E target) {
        int l = 0, r = arr.length - 1;
        while(l <= r) { // 数组中存在元素时
            int mid = l + ( r - l) / 2;
            if(arr[mid].compareTo(target) == 0) { // 刚好中间的元素就是
                return mid;
            }
            if(arr[mid].compareTo(target) > 0) { // 中间的元素小于target，接着查找右边的列表
                r = mid - 1;
            }else { // 中间的元素大于target, 接着查找左边的列表
                l = mid + 1;
            }
        }
        return -1;
    }

/**
 * 查找大于target的最小值
 * @param arr
 * @param target
 */
public static <E extends Comparable<E>> int upper(E[] arr, E target) {
    int l = 0, r = arr.length;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid].compareTo(target) == 0) {
            return mid + 1;
        }else if(arr[mid].compareTo(target) > 0) { // 这个r = mid是因为mid的位置可能是目标值
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    // l和r最后都都指向同一个位置。没找到则返回arr.length
    return l;
}

public static <E extends Comparable<E>> int ceil(E[] arr, E target) {
        int index = upper(arr, target);
        if(arr[index - 1].compareTo(target) == 0) {
            return index - 1;
        }
        return index;
    }

/**
     * 使用二分法，解决leetCode875
     * @param piles
     * @return
     */
    public static int leetCode875(int[] piles, int h) {
        // 假设他先吃二分法中间的那个根数
        int l = 1; // 最少吃一根
        int r = Arrays.stream(piles).max().getAsInt(); // 假设吃数组中最大数量的根数
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(eatingTime(piles, mid) <= h) { // 此时mid可能会目标值
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }
    public static int eatingTime(int[] arr, int k) {
        int res = 0;
        for(int pile: arr) {
            res = res + pile / k + (pile % k > 0 ? 1 : 0);
        }
        return res;
    }