MENU

php二分查找算法实现类似QQ升级功能

• July 26, 2018 • php,技术杂谈阅读设置

最近工作项目上遇到一个类似根据用户在线时长增加经验并升级的功能。

需求如下:

  1. 每一小时为用户增加10点经验
  2. 当用户经验增加到一定数值该用户自动升级

如上所述:

首先我们需要2张表

1.用户等级表 user_level,用于保存用户当前等级及经验值
字段:id 主键 | uid 用户id | now_level当前等级| exp 当前经验值

2.等级经验对照表 level_exp,用于区别多少等级对照多少经验,例如1-200经验值为等级1 ,201-300经验值为等级2
字段:id 主键 | level等级 | mix 起始经验值 | max 结束经验值

思路:
每当为用户增加经验后,拿到该用户目前的总经验值。(例如我目前总经验值为200 加上10点经验后就等于210点,这个时候我就该升级了。)
然后我们把该用户的总经验值进行二分查找,判断该用户总经验值属于哪个等级的,比如我刚刚加了10点经验,我现在的总经验值是210,这个时候就需要去level_exp表里算出该用户隶属于哪个等级。
拿到等级后再与当前等级进行对比,如果值一样,则代表还不能升级,如果不一样,则将用户等级修改为对应经验的等级。

二分查找算法示例:

    /**
 * 二分查找法
 * @param $score 经验
 * @param $filter 经验对应等级集合
 * @return array
 */
function levelSearch($score, $filter)
{
    $half = floor(count($filter) / 2); // 取出中間数

    // 判断积分在哪个区间
    if ($score <= $filter[$half - 1]['max']) {
        $filter = array_slice($filter, 0 , $half);
    } else {
        $filter = array_slice($filter, $half , count($filter));
    }

    // 继续递归直到只剩一个元素
    if (count($filter) != 1) {
        $filter = levelSearch($score, $filter);
    }
    return $filter;
}

实现:

// 经验对应等级集合
$filter = [
['level' => 1, 'min' => 1, 'max' => 50],
['level' => 2, 'min' => 51, 'max' => 110],
['level' => 3, 'min' => 111, 'max' => 180],
['level' => 4, 'min' => 181, 'max' => 260],
['level' => 5, 'min' => 261, 'max' => 500],
];
$result = levelSearch(240, $filter);
// 该分数对应的等级
echo current($result)['level'];
Archives QR Code
QR Code for this page
Tipping QR Code