ある範囲に含まれている整数の個数《二分探索》

【値の探索】コード 1/2

reader.on('close', () => {
   const binary_search = (A, n, k) => {  // A = ソート済の数列, n = 数列のサイズ, k = 探索する値
      let [left, right] = [0, n];  // left = 探索範囲の左端, right = 探索範囲の右端
      while (left <= right) {
         const mid = Math.floor((left + right) / 2);  // mid = 探索範囲(left ~ right)の中央
         if (A[mid] === k) {  // mid が k なら…
            return true;  // true を返す
         } else if (A[mid] > k) {  // 探索範囲の中央が k より大きければ…
            right = mid - 1;  // right (範囲の右端)を mid - 1 へ移動 (検索範囲をA[mid]より小さい値に限定)
         } else {  // 探索範囲の中央が k より小きければ
            left = mid + 1;  // left (範囲の左端)を mid + 1 へ移動 (検索範囲をA[mid]より大きい値に限定)
         }
      }
      return false;
   };
   const [n, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number);
   for (let i = 3; i < q + 3; i++) {
      const k = Number(lines[i]);
      if (A[0] === k || A[n - 1] === k) {
         console.log('Yes');
      } else {
         console.log(binary_search(A, n - 1, k) ? 'Yes' : 'No');
      }
   }
});

問題文の模擬コード通りだと こんな感じになりました。

【値の探索】コード 2/2

reader.on('close', () => {
   const binary_search = (left, right, k) => {  // left = 探索範囲の左端, right = 探索範囲の右端, k = 探索する値
      if (left > right) {  // left(探索範囲の左端)が right (探索範囲の右端)より大きくなれば…
         return false;  // k は含まれていなかったことになるので false を返す
      }
      const mid = Math.floor((left + right) / 2);  // 探索範囲(left ~ right)の中央
      if (A[mid] === k) {  // A[mid]が k なら…
         return true;  // true を返す
      } else if (A[mid] > k) {  // 範囲の中央の値が k より大きければ…
          return binary_search(left, mid - 1, k);  // right を mid - 1 にして再帰呼出し
      } else if (A[mid] < k) {  // 範囲の中央が k より小さければ
          return binary_search(mid + 1, right, k);  // left を mid + 1 にして再帰呼出し
      }
   };
   const [n, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number);
   for (let i = 3; i < q + 3; i++) {
      if (A[0] === k || A[n - 1] === k) {
         console.log('Yes');
      } else {
         console.log(binary_search(0, n - 1, k) ? 'Yes' : 'No');
      }
   }
});

再起関数にするとこんな感じ？

【lower_bound】コード 1/3

reader.on('close', () => {
   const binary_search = (a, n, k) => {  // a = 配列(テストの点数・降順), n = 要素数 - 1, k = 検索する値
      let [left, right] = [0, n];  // left = 合格判定済のindex, right = 探索範囲の右端
      while (left < right) {
         const mid = Math.ceil((left + right) / 2);  // (left + right) / 2 を 切り上げ const mid = Math.floor((left + right) / 2); // (left + right) / 2 を 切り上げ
         // const mid = Math.floor((left + right) / 2); // (left + right) / 2 を 切り下げ
         if (a[mid] < k) {  // a[mid]が k 未満ならa[mid]〜は不合格なので…
            right = mid - 1;  // right (範囲の右端)を mid - 1 へ移動 (検索範囲をA[mid]より大きい値に限定)
            // right = mid; 
         } else {  // a[mid]が k 以上なら a[mid]まで合格が確定するので…
            left = mid;  // left (合格判定済のindex)は mid
            // left = mid + 1;
         }
      }
      return left;  // a[left]まで合格が確定
    };
   const [N, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number).sort((s, b) => b - s);  // 降順ソート
   for (let i = 3; i < q + 3; i++) {
      const K = Number(lines[i]);  // K 点以上で合格
      if (A[0] < K) {  // A の先頭の値が K 未満なら…
         console.log(0);  // 合格者 なし
      } else if (A[N - 1] >= K) {  // A の後尾の値が K 点以上なら…
         console.log(N);  // 全員合格
      } else {  // それ以外
         console.log(binary_search(A, N - 1, K) + 1);  // 合格者の人数
         // console.log(binary_search(A, N - 1, K));
      }
   }
});

k_i 点以上の人数を求めたいので 配列 A を 大きい順に並べて二分探索しました。k_i 点の人も含むので mid の値は (left + right) / 2 を 切り上げて求めた上で left の値を return しています。

【lower_bound】コード 2/3

reader.on('close', () => {
   const binary_search = (a, n, k) => {  // a = 数列(昇順), n = a の要素数 - 1, k = 合格点
      let [left, right] = [0, n];  // left = 不合格ライン, right = 不合格ライン
      while (left < right) {  // left が right) より小さい間…
         const mid = Math.floor((left + right) / 2);  // mid = 探索範囲(left ~ right)の中央
         if (a[mid] < k) {  // a[mid]が k 未満なら a[0] ~ a[mid]は不合格なので…
            left = mid + 1;  // a[0] ~ a[mid]は除外
         } else if (a[mid] >= k) {  // a[mid]が k 以上なら…
            right = mid;  // a[0] ~ a[mid] ~ 合格
         }
      }
      return right;  // a[right] ~ 合格
   };
   const [N, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number).sort((s, b) => s - b);
   for (let i = 3; i < q + 3; i++) {
      const k = Number(lines[i]);
      if (A[N - 1] < k) {
         console.log(0);
      } else if (A[0] >= k) {
         console.log(N);
      } else {
         const border = binary_search(A, N, k);  // 合格者の最小index(不合格者数) 
         console.log(N - border);  // N - 不合格者数 = 合格者数
      }
   }
});

問題文の模擬コードを参照しています。

【lower_bound】コード3/3

reader.on('close', () => {
   const binary_search = (a, left, right, k) => {
      if (left >= right) {
         return right;
      }
      const mid = Math.floor((left + right) / 2);
      if (a[mid] < k) { 
         return binary_search(a, mid + 1, right, k);
      } else {
         return binary_search(a, left, mid, k);
      }
   };
   const [N, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number).sort((s, b) => s - b);
   for (let i = 3; i < q + 3; i++) {
      const k = Number(lines[i]);
      const border = binary_search(A, 0, N, k);
      console.log(N - border);
   }
});

コード 2/3を再起関数にするとこんな感じになりました。

【upper_bound】コード

reader.on('close', () => {
   const binary_search = (A, n, k) => {
      let [left, right] = [0, n];
      while (left < right) {
         let mid = Math.floor((left + right) / 2);
         if (A[mid] <= k) {
            left = mid + 1;
         } else {
            right = mid;
         }
      }
      return right;
   };
   const [n, q] = [lines[0], lines[2]].map(Number);
   const A = lines[1].split(' ').map(Number).sort((s, b) => s - b);
   for (let i = 3; i < q + 3; i++) {
      const k = Number(lines[i]);
      if (A[0] <= K) {  // A の先頭の値が K 以下なら…
         console.log(0);  // 合格者 なし
      } else if (A[N - 1] > K) {  // A の後尾の値が K より高得点なら…
         console.log(N);  // 全員合格
      } else {  // それ以外
         const border = binary_search(A, n, k);
         console.log(n - border);
      }
   }
});

【STEP: 3】の コード中の不等号記号が変えただけ…。

【ある範囲に含まれている整数の個数】コード

reader.on('close', () => {
   const binary_search_lo = (A, n, k) => {
      let [left, right] = [0, n];
      while (left < right) {
         let mid = Math.ceil((left + right) / 2);
         if (A[mid] < k) {
            right = mid - 1;
         } else {
            left = mid;
         }
      }
      return left;
   };

   const binary_search_up = (A, n, k) => {
      let [left, right] = [0, n];
      while (left < right) {
         const mid = Math.ceil((left + right) / 2);
         if (A[mid] <= k) {
            right = mid - 1;
         } else {
            left = mid;
         }
      }
      return left;
   };
   const [n, q] = [lines[0], lines[2]].map(Number);
   const A = [0, ...lines[1].split(' ').map(Number).sort((s, b) => b - s)];
   for (let i = 3; i < q + 3; i++) {
      const [l, r] = lines[i].split(' ').map(Number);
      const over = binary_search_lo(A, n, l);
      const less = n - binary_search_up(A, n, r);
      console.log(over + less - n);
      // console.log(over, less);
   }
});

とりあえずup。