有重复值的二分查找

最近在验证SQL join的算法，感觉在内存中实现的话，比较高效的方法就是二分查找了。

但与普通二分查找不同，SQL join的时候左右两边的值可能会有重复，这些重复值都是要找到的。

所以我对二分查找进行了升级优化，不再返还一个索引，而是返回一个索引范围，找不到就返回null

实现了两个版本：

1.递归二分查找

2.while循环二分查找

 /**
     * 带重复值的二分查找，返回目标所在的索引范围
     * 二分查找-递归版本
     *
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static <T extends Comparable<T>> Range binarySearch2(List<T> arr, int left, int right, T findVal) {
        // 当left > right 时，说明递归整个数组没有找到
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        T midVal = arr.get(mid);

        if (midVal.compareTo(findVal) > 0) {
            return binarySearch2(arr, left, mid - 1, findVal);
        } else if (midVal.compareTo(findVal) < 0) {
            return binarySearch2(arr, mid + 1, right, findVal);
        } else {
            Range range = new Range();
            range.setStart(mid);
            range.setEnd(mid);
            // 先让temp向左移
            int temp = mid - 1;
            while (temp >= 0 && arr.get(temp).equals(findVal)) {
                // 否则，就把temp放进resIndex中
                range.setStart(temp);
                temp -= 1; // temp 左移
            }
            //temp右移
            temp = mid + 1;
            while (temp < arr.size() && arr.get(temp).equals(findVal)) {
                range.setEnd(temp);
                temp += 1; // temp 左移
            }
            return range;

        }

    }

    /**
     * 有重复值的二分查找，while循环版本
     *
     * @param des
     * @return
     */
    public static <T extends Comparable<T>> Range binarySearch(List<T> arr, T des) {
        //定义初始最小、最大索引
        int start = 0;
        int end = arr.size() - 1;
        int mid = -1;
        //确保不会出现重复查找，越界
        while (start <= end) {
            //计算出中间索引值
            int middle = (end + start) / 2;//防止溢出
            if (des.equals(arr.get(middle))) {
                mid = middle;
            } else if (des.compareTo(arr.get(middle)) < 0) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        //没找到，返回null
        if (mid == -1) {
            return null;
        }
        Range range = new Range();
        range.setStart(mid);
        range.setEnd(mid);
        // 先让temp向左移
        int temp = mid - 1;
        while (temp >= 0 && arr.get(temp).equals(des)) {
            // 否则，就把temp放进resIndex中
            range.setStart(temp);
            temp -= 1; // temp 左移
        }
        //temp右移
        temp = mid + 1;
        while (temp < arr.size() && arr.get(temp).equals(des)) {
            range.setEnd(temp);
            temp += 1; // temp 左移
        }
        return range;

    }

    /**
     * 目标索引范围，左闭右闭区间
     */
    @Data
    static class Range {
        private int start;
        private int end;
    }