最简单二分查找

由于二分查找原来比较简单，不图解原理了，直接上代码

循环实现

/**
     * 简单循环二分查找
     *
     * @param list
     * @param low
     * @param high
     * @param value
     */
    public static int simpleSearch(int[] list, int low, int high, int value) {

        while (low <= high ) {
            int middle = low + (high - low) / 2;

            if (list[middle] == value) {
                return middle;
            }

            if (list[middle] < value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        return -1;
    }

递归实现

/**
     * 递归二分查找
     *
     * @param list
     * @param low
     * @param high
     * @param value
     * @return
     */
    public static int recursionSearch(int[] list, int low, int high, int value) {

        if (low > high) {
            return -1;
        }

        int middle = low + (high - low) / 2;

        if (list[middle] == value) {
            return middle;
        }

        if (list[middle] < value) {
            return recursionSearch(list, middle + 1, high, value);
        } else {
            return recursionSearch(list, low , middle - 1, value);
        }
    }

查询第一个值等于给定值的元素

/**
     * 查询第一个相等的值
     *
     * @param list
     * @param low
     * @param high
     * @param value
     * @return
     */
    public static int firstSearch(int[] list, int low, int high, int value) {

        while (low <= high) {

            int middle = low + (high - low) / 2;

            if (list[middle] > value) {
                high = middle - 1;
            } else if (list[middle] < value) {
                low = middle + 1;
            } else {
                // 此时 当前节点 等于 value

                // 当前节点是第一个节点，那就它了
                if (middle == low) {
                    return middle;
                }

                // 如果当前节点的前一个节点不等，那就它了
                if (list[middle -1] != value) {
                    return middle;
                }

                // 不然，接着往左挪(因为选第一个相等的)
                high = middle - 1;
            }
        }

        return -1;
    }

查询最后一个值等于给定值的元素

/**
     * 查询最后一个相等的值
     *
     * @param list
     * @param low
     * @param high
     * @param value
     * @return
     */
    public static int lastSearch(int[] list, int low, int high, int value) {

        while (low <= high) {

            int middle = low + (high - low) / 2;

            if (list[middle] > value) {
                high = middle - 1;
            } else if (list[middle]  < value) {
                low = middle + 1;
            } else {

                // 此时 当前节点 等于 value

                // 当前节点是最后一个节点，那就它了
                if (middle == high) {
                    return middle;
                }

                // 如果当前节点的后一个节点不等，那就它了
                if (list[middle + 1] != value) {
                    return middle;
                }

                // 不然，接着往右挪(因为选最后一个相等的)
                low = middle + 1;
            }
        }

        return -1;
    }

查询第一个值大于给定值的元素

/**
     * 查询第一个大于的值
     *
     * @param list
     * @param low
     * @param high
     * @param value
     * @return
     */
    public static int firstGreaterSearch(int[] list, int low, int high, int value) {

        while (low <= high) {

            int middle = low + (high - low) / 2;

            if (list[middle] >= value) {

                // 此时 当前节点 是大于等于 value

                // 如果当前节点大于 且 当前节点的前一个小于等于 那就它了
                if (list[middle] > value && list[middle - 1] <= value) {
                    return middle;
                } else {
                    // 不然， 接着往右挪(因为选的是大于，大于肯定在右边)
                    low = middle + 1;
                }

            } else {
                high = middle - 1;
            }
        }

        return -1;
    }

查询最后一个值小于给定值的元素

/**
     * 查询最后一个小于
     *
     * @param list
     * @param low
     * @param high
     * @param value
     * @return
     */
    public static int lastLessSearch(int[] list, int low, int high, int value) {

        while (low <= high) {

            int middle = low + (high - low) / 2;

            if (list[middle] > value) {
                low = middle - 1;
            } else {
                // 现在是 小于等于

                // 如果当前小于 且 当前+1 大于等于 那么就是它了
                if (list[middle] < value && list[middle + 1] >= value) {
                    return middle;
                } else {
                    // 不然，接着往左挪(因为选的最后一个小于，因为小于肯定在左边)
                    high = middle - 1;
                }
            }
        }

        return -1;
    }

代码github

https://github.com/handsomebai/arithmetic