1

我需要使用玩家拥有的经验值和经验图表来了解玩家的等级。我想以最有效的方式做到这一点。这就是我得到的。注意：真实的 expChart 有数千个级别/索引。所有值都按递增顺序排列。

var expChart = [1,10,23,54,65,78,233,544,7666,22224,64654,456456,1123442];
/*
lvl 0: //0-1[ exp
lvl 1: //[1-10[ exp
lvl 2: //[10-23[ exp
*/
getLvlViaExp = function(exp){
    for(var i = 0 ; i < expChart.length ; i++){
        if(exp < expChart[i]) break;
    }
    return i;
}

这是一种更有效的方法。每 x 步（例如 6 步，可能每数百步使用真实图表），我进行快速比较并跳转到近似索引，跳过许多索引。

getLvlViaExp = function(exp){
    var start = 0;
    if(exp > 233)   start = 6;
    if(exp > 1123442) start = 12;

    for(var i = start ; i < expChart.length ; i++){
        if(exp < expChart[i]) break;
    }
    return i;
}

有没有更好的方法来做到这一点？

解决方案：

Array.prototype.binarySearch = function(value){
    var startIndex  = 0,
        stopIndex   = this.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);
    if(value < this[0]) return 0;
    while(!(value >= this[middle] && value < this[middle+1]) && startIndex < stopIndex){

        if (value < this[middle]){
            stopIndex = middle - 1;
        } else if (value > this[middle]){
            startIndex = middle + 1;
        }

        middle = Math.floor((stopIndex + startIndex)/2);
    }

    return middle+1;
}
4

2 回答 2

4

搜索的最佳算法是 O(lg n) 的二进制搜索（除非您可以使用 O(c) 的散列搜索来做到这一点。

http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

基本上跳到图表的中间（n / 2）。你是从那个数字中体验到更高还是更低。如果更高跳到中间的上半部分。如果下跳到下半部分的中间：比较并重复，直到找到你要找的东西。

于 2013-10-18T02:24:15.147 回答
0 
var expChart = [1,10,23,54,65,78,233,544,7666,22224,64654,456456,1123442];
getLvlViaExp = function(exp){
    var min=0;
    var max=expChart.length-1;
    var i;
    while(min <=max){

    i=Math.round((min+max)/2); 
        //document.write("<br />"+i+":"+min+":"+max+"<br />");
        if(exp>=expChart[i] && exp <=expChart[i+1]) {
        break;
        }
    if(exp>=expChart[i]){
            min=i+1;
        }
    if(exp<=expChart[i]){
            max=i-1;

        }

    }
return i;
}

document.write(getLvlViaExp("10"));

我已经对其进行了测试，它似乎工作得很好。如果您想查看它实际执行了多少步骤才能得到答案，请在 while 循环中取消对 document.write 的注释。看着它有点迷人。

于 2013-10-18T03:30:04.167 回答