递归使用的浏览器ES6二进制搜索

Question

我想实现递归使用Javascript二进制搜索。

假设该阵列被排序。

函数签名可以是这样的：

BinarySearchRecursively (ArrayGiven, x, p, r)

其中ArrayGiven是一个数组，x是我们正在寻找的数字。 p为起始索引，r是结束索引。

任何Jsbin /的jsfiddle链路将高度赞赏。

Answer 1

下面是我如何实现它。随着伪代码在顶部的意见执行。

这是JS斌：https://jsbin.com/womenov/3/edit?js,console任何意见，将不胜感激。

/**
 * Binary Search using Recursion
 * p.......q........r : range where p is start, r is end
 * Assume the array is sorted.
 * Procedure BinarySearchRecursively(ArrayGiven, x, p, r, q = 0)
 * if(p > r) return -1
 * q = Math.floor((p+r)/2)
 * if(x === ArrayGiven[q]) return q
 * else if(x > ArrayGiven[q]) set p = q+1
 *    return BinarySearchRecursively(ArrayGiven, x, q + 1, r)
 * else r = q-1 return BinarySearchRecursively(ArrayGiven, x, p, q-1)
 *
 */

function BinarySearchRecursively (ArrayGiven, x, p, r, q = 0) {
        if (p > r) {
            return -1;
        }
        q = Math.floor((p+r)/2);
    if (x === ArrayGiven[q]) {
        return q;
    }
    if (x > ArrayGiven[q]) {
        return BinarySearchRecursively(ArrayGiven, x,q+1, r);
    }
    return BinarySearchRecursively(ArrayGiven, x, p,q-1);
}

const TestArray = [2, 6, 8, 9, 11, 15];
console.log(`Given Element is at position : ${BinarySearchRecursively(TestArray, 2, 0,5)}`);