paizaラーニング レベルアップ問題集 二分探索メニュー JavaScript ある範囲に含まれている整数の個数

ある範囲に含まれている整数の個数 (paizaランク B 相当)

解答例(Python3 の場合参考)

前問までのbinary_search関数は、指定した値が最初に現れる位置を求めるものです。
なので、前問までで学習した lower_bound や upper_bound を用いることができます。
l_i以上の値が最初に現れる位置lpos(l positionの略)を求める→lower_bound
r_iより大きい値が最初に現れる位置rpos(r positionの略)を求める→upper_bound
l_i以上r_i以下に含まれる整数の個数は、rpos-lposで求まります。

(または、r_iが最初に現れる位置をrpos1とすると、答えはrpos1-lpos+1でも求まります)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//二分探索の関数定義
const binary_search = (A, n, k) => {//(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    let left = 0;
    let right = n;
    
    // 探索範囲を狭めていく
    while (left < right) {
        // 探索範囲の中央
        const mid = Math.floor((left + right) / 2);

        if (A[mid] < k) {
            left = mid+1;
        } else {
            right = mid;
        }    
    }
    // 狭め終わったら最初に現れた位置を返す
    return right;
};

//メイン
const n = Number(lines[0]);
const A = lines[1].split(" ").map(Number).sort((a, b) => a - b);
const q = Number(lines[2]);

//各l,rについて調べる
for (let i = 1; i <= q; i++) {
  const [l, r] = lines[i + 2].split(" ").map(Number);
  const lpos = binary_search(A, n, l);
  const rpos = binary_search(A, n, r + 1);//r+1はrより大きい数
  console.log(rpos - lpos);
}