Java实现二分查找:递归和非递归

二分查找的前提是数组已经是排好序的了

递归方式

 /**
     * 二分查找_递归
     *
     * @param array 排序好的数组
     * @param low   数组下标
     * @param high  数组下标
     * @param key   要查找的值
     * @return 返回数组下标, 找不到返回-1
     */
    static int binarySearchRecursion(int array[], int low, int high, int key) {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (array[mid] > key)
            return binarySearchRecursion(array, low, mid - 1, key);
        if (array[mid] < key)
            return binarySearchRecursion(array, mid + 1, high, key);
        return mid;
    }

非递归方式

    /**
     * 二分查找_非递归
     */
    static int binarySearchNonRecursion(int array[], int low, int high, int key) {
        while (low < high) {
            int mid = (low + high) / 2;
            if (array[mid] > key)
                high = mid - 1;
            else if (array[mid] < key)
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }

标签: 二分查找, 算法

相关文章推荐: