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

lower_bound (paizaランク B 相当)

解答例

問題文の擬似コードに沿って実装します。
なお、2023/01/12時点で、問題文の疑似コードで、数列についてAとaが混在していました。

binary_search(A : 数列, n : 数列のサイズ, k : 基準)

ー中略ー

 if a[mid] < k then
            // a[0] ~ a[mid] は k 未満なので調べる必要が無い

となっている部分です。これはAかaどちらかに決めて実装します。運営に問い合わせ済みです。

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

//二分探索の関数定義
/**
    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) {
        // 探索範囲の中央
        const 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;
};

//メイン
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);
  console.log(n - min_i);
}