Java实现二分查找

Java实现二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

这里我们实现最简单情况下的二分查找。升序排列的数组，无重复元素，查找其中是否包含单个元素。
非递归方式实现：

    /**
     * 二分查找，针对不存在重复元素的。非递归实现。
     *
     * @param a     升序数组
     * @param n     数组大小
     * @param value 要查找的数值
     * @return 返回值表示要查找的数据在数组中的角标，如果没有则返回-1.
     */
    public static int binarySearch1(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

当然，也可以使用递归方式实现：

    /**
     * 二分查找，针对不存在重复元素的。递归实现。
     *
     * @param a     升序数组
     * @param n     数组大小
     * @param value 要查找的数值
     * @return 返回值表示要查找的数据在数组中的角标，如果没有则返回-1.
     */
    public static int binarySearch2(int[] a, int n, int value) {
        return binarySearchInternally(a, 0, n - 1, value);
    }

    private static int binarySearchInternally(int[] a, int low, int high, int value) {
        if (low > high) {
            return -1;
        }

        int mid = low + ((high - low) >> 1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            return binarySearchInternally(a, mid + 1, high, value);
        } else {
            return binarySearchInternally(a, low, mid - 1, value);
        }
    }