bs.ts

function bs(nums: number[], x: number) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const k = Math.floor((left + right) / 2);
        if (nums[k] === x) return k;
        if (nums[k] < x) left = k + 1;
        else right = k - 1;
    }
    return -1;
}

function bs2(nums: number[], x: number) {
    let k = 0;
    const div2 = (n: number) => Math.floor(n / 2);
    for (let len = div2(nums.length); len >= 1; len = div2(len)){
        while((k + len) < nums.length && nums[k + len] <= x) k += len;
    }
    return k;
}