javascript实现二分查找失败是为什么？

实现代码:

Array.prototype.binary_search = function(low, high, key) {
    var mid = parseInt((high + low) / 2),
          low = low,
          high = high,
          key = key;
    if(low > high)
        return -1;
    else {
        if(key == this[mid])
            return mid;
        else if(key > this[mid])
            this.binary_search(mid+1, high, key);
        else
            this.binary_search(low, mid-1, key);
    }
}

---

你后面的代码没有 return

        else if(key > this[mid])
            this.binary_search(mid+1, high, key);
        else
            this.binary_search(low, mid-1, key);

即当你要找的那个值, 不是正好在中间的时候, 走了 左/右的 查询, 你没有把值返回回去..

要找的 key 正好在中间,
和不在中间的, 因为没有return, 所以找到了值, 也返回不回去..

加了 return 之后的效果:

---

代码再简化一下, 流程更清晰.

Array.prototype.binary_search = function(low, high, key) {
    var mid = parseInt((high + low) / 2);

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

    if(key == this[mid]){
        return mid;
    }

    if(key > this[mid]){
        return this.binary_search(mid+1, high, key);
    }

    return this.binary_search(low, mid-1, key);
}