欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-02 11:18:18
...

      效率最高的查找方法-折半查找,也叫做二分法查找;可以在最短时间内找到一个数字在一个数组中的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  希望对大家有帮助