用JS实现效率最高的查找-折半查找的改进(可以查到不在数组中的值的位置)

      效率最高的查找方法-折半查找，也叫做二分法查找；可以在最短时间内找到一个数字在一个数组中的index定位，但有些时候我们需要实现一个不在数组中的值“将”位于已有数组中的第几位的场景，下面是我用JS实现的代码，对于折半查找的原理请百度或者google一下，当然360也是可以的。

 

// 计算index
var _myIndex = function(list, key) {
    var low = 0;
    var high = list.length - 1;
    var mid;
    var result = 0;

    // 只有一个数字
    if (low == high) {
        if (list[0] > key) {
            return 2;
        } else {
            return 1;
        }
    }
    while (low <= high) {
        mid = parseInt((low + high) / 2);
        if (list[mid] > key) {
            low = mid + 1;
            if (low > high) {
                result = mid + 1;
                break;
            }
            ;
        } else if (list[mid] < key) {
            high = mid - 1;
            if (low > high) {
                result = mid;
                break;
            }
            ;
        } else {
            result = mid;
            break;
        }
        ;
    }
    ;// 循环结束

    // 返回index
    return result;
};

 

可以使用测试数组测一下：

var list = [1,3,5,7,9];

var key = 8;

有问题可以给我留言  更欢迎大家提BUG  希望对大家有帮助

评论

1 楼 alice_king 2013-10-20