JavaScript 查找有序数列中缺少的最小值

最近有一个需求，需要在获取一个可用id 在0~max值范围内，且有数量限制。 该id可以被删除， 删除后新的id应补位。这里举一个例子。

规则：
比如现在一个id 都没有用则 获取到的id为0
[0]
如果继续获取则为1
[0, 1]
如果继续获取则为2
[0,1,2]
继续获取则为3
[0,1,2,3]
现在删除1
[0,2,3]
再次获取则为1，在获取则为4
[0,1,2,3,4]
现在删除1,3
[0,2,4]
再次获取4次则为1,3,5,6
[0,1,2,3,4,5,6]

实质上就是查找有序数列中缺少的最小值问题。当然这里数量限制不能较大，因为有遍历操作，较大用数组就比较吃亏了。

首先，数列要有序才方便处理，这里就涉及到第一个问题，我们存进去就保证有序，还是读出来排序来保证有序。实质上个人觉得应该是存进去有序，通常情况下都是读的次数大于写。

这里简单写了部分基础逻辑，还有优化的空间

class Ids{
    constructor(options) {
        this.idStart = options.idstart;
        this.idMax = options.idMax;
        this.idNumLimit = options.idNumLimit;
        this.ids = [];
    }

    getId(){
        return new Promise((resolve, reject)=>{
            let idsLength = this.ids.length;//已经是一波遍历了？
            if(idsLength === 0)
                return resolve(this.idStart);
            if(idsLength>this.idNumLimit)
                return reject("ID exceeds quantity limit");

            if(this.ids[idsLength-1] === this.idStart + (idsLength-1)){//有序数组中没有任何缺失  则直接在末尾数值+1即可。
                let newId = this.ids[idsLength-1] + 1;
                if(newId > this.idMax )
                    return reject("ID exceeds maximum")
                else
                    return resolve(newId);
            }   
    
            //因为数组有序 实质上这里可以用2分查找方式进行优化
            let minId = this.idStart; //一个判断id是否连续的算法 不连续则在最小不连续加1 则为需要值
            for (let id of this.ids){
                if((id - minId) > 1){
                    break;
                }
                minId = id;
            }

            return resolve(minId+1);
        });
    }


    deleteId(id){
        return new Promise((resolve, reject)=>{
            let idIndex = this.ids.findIndex((element)=>element === id);//该方法是遍历 效率对于有序数列并不高  可以利用有序数组的特点优化
            if(idIndex === -1) 
                reject("id no exit");
            this.ids.splice(idIndex, 1);//移除该faceid
            return resolve();
        });
    }

    setId(id){
        return new Promise((resolve, reject)=>{
            let idInsertIndex = id - this.idStart;//得到插入位置
            this.ids.splice(idInsertIndex, 0, id);
            return resolve();
        });
    }
}

下面提供测试代码，测试为文首基本情况

const  run =async function(){
    let ids = new Ids({idstart:0, idMax:200, idNumLimit:10});
    console.info("\n现在一个id 都没有用则 获取到的id为0");  
    let id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);

    console.info("\n如果继续获取则为1");  
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);

    console.info("\n如果继续获取则为2 "); //如果继续获取则为2 
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);

    console.info("\n继续获取则为3"); //
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);

    console.info("\n现在删除1"); //
    await ids.deleteId(1);
    console.info(ids.ids);


    console.info("\n再次获取则为1，在获取则为4"); 
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
  
    console.info("\n现在删除1,3");
    await ids.deleteId(1);
    await ids.deleteId(3);
    console.info(ids.ids);

    console.info("\n再次获取4次则为1,3,5,6");
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
    id = await ids.getId();
    await ids.setId(id);
    console.info(ids.ids);
}

run();