paizaラーニング レベルアップ問題集 二分探索メニュー JavaScript upper_bound

upper_bound (paizaランク B 相当)

注釈

解答例が２つありますが、解答例２の方が、lower_boundと関数を共通で使えるので、より好ましいと思われます。

解答例

STEP: 2 lower_bound　の"未満"が、本問題では"以下"になったので、そこだけ修正します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const n = Number(lines[0]);
const A = lines[1].split(" ").map(Number).sort((a, b) => a - b);

//二分探索の関数定義
/**
    A_i > k を満たす最小の i を返す
    A_i > k を満たす i が存在しない場合は n を返す
*/
const binary_search = (A, n, k) => {//(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    let left = 0;
    let right = n;
    
    // 探索範囲を狭めていく
    while (left < right) {
        // 探索範囲の中央
        mid = Math.trunc((left + right) / 2);

        if (A[mid] <= k) {
            // A[0] ~ A[mid] は k 以下なので調べる必要が無い
            left = mid+1;
        } else {
            right = mid;
        }    
    }
    // 狭め終わったらmin_iを返す
    return right;
};

//各kについて調べる
const q = Number(lines[2]);
for (let i = 1; i <= q; i++) {
  const k = Number(lines[i + 2]);
  const min_i = binary_search(A, n, k);
  console.log(n - min_i);
}

解答例2

また、k点より大きい点数k+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;
        }    
    }
    // 狭め終わったらmin_iを返す
    return right;
};

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

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