今回は paiza の「ソートと検索 (query)」の問題に挑戦！
普通に解いたら簡単すぎたので、他の解き方で、「二分探索」の関数を作って解いてみた！
問題概要
- クラスには最初に N 人の生徒がいる。
- paiza 君（身長 P）がいるので、合計 N + 1 人。
- このクラスには次のようなイベントが合計 K 回起こる
イベント
- join num
新しい身長の生徒がクラスに加わる。
- sorting
全員で背の順に並べる → paiza 君の位置を出力する。
入力例:
3 3 176
118
174
133
join 137
join 177
sorting
出力例:
5
✅ OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, K, P] = lines[0].split(' ').map(Number);
const heights = lines.slice(1, N+1).map(Number);
heights.push(P);
const events = lines.slice(N+1);
for(const e of events){
const [command, num] = e.split(' ');
const h = Number(num);
if (command === 'join'){
heights.push(h);
}
else if (command === 'sorting'){
heights.sort((a,b) => a - b);
console.log(heights.indexOf(P) + 1);
}
}
});
-
.push join
イベントで新しい身長を配列に追加。 -
.sort sorting
イベントで配列を昇順に並び替える。 -
.indexOf
並び替えた後、paiza 君の身長 P の位置を探す。 -
+1
.indexOfは0始まり → 「前から何番目」にするには+1する。
✅ OK例： 二分探索
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line));
rl.on('close', () => {
const [N, K, P] = lines[0].split(' ').map(Number);
const heights = lines.slice(1, N + 1).map(Number);
heights.push(P);
heights.sort((a, b) => a - b);
const events = lines.slice(N + 1);
for (const e of events) {
const [command, num] = e.split(' ');
const h = Number(num);
if (command === 'join') {
// 転校生が来たら、正しい位置に挿入する
insertSorted(heights, h);
}
else if (command === 'sorting') {
// すでに昇順なので、そのまま indexOf で paiza君の位置を探す
console.log(heights.indexOf(P) + 1);
}
}
});
function insertSorted(arr, value) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] >= value) {
right = mid;
}
else {
left = mid + 1;
}
}
arr.splice(left, 0, value);
}
-
insertSorted
二分探索でソート済み配列に正しい位置へ追加。 -
heights
常にソート状態なので、sortingイベントでソート不要！ -
.indexOf(P) + 1
paiza 君の位置をそのままで探せる。
💡 二分探索（バイナリサーチ）
ソートされた配列やリストの中から、特定の要素を効率的に探すアルゴリズム。
配列の中央の値と比較し、探している値が中央の値よりも大きいか小さいかで、探索範囲を半分に絞り込み、この操作を繰り返すことで、目的の値を見つけ出す方法。
🔍 今回のコード
/*
* 二分探索で「昇順ソート済み配列」に要素を正しい位置に挿入する
*
* @param {number[]} arr - ソート済み配列（昇順）
* @param {number} value - 挿入する値
*/
function insertSorted(arr, value) {
// 探索範囲の左端
let left = 0;
// 探索範囲の右端（配列の長さ）
let right = arr.length;
// 探索範囲を半分に絞っていく
while (left < right) {
// 中央のインデックス（探索範囲の中央）
const mid = Math.floor((left + right) / 2);
// 中央の値と比較
if (arr[mid] >= value) {
// 中央の値が大きい or 等しい場合 → 挿入位置は左側にある
right = mid;
}
else {
// 中央の値が小さい場合 → 挿入位置は右側にある
left = mid + 1;
}
}
// left と right が一致した場所が「挿入すべき位置」
// splice で配列に value を追加（0個削除して value を挿入）
arr.splice(left, 0, value);
}
🔍 例で整理
例：
arr = [1, 3, 5, 7, 9]
value = 4
ここでやりたいのは：
→ 4 は どこに挿入されればソート順が崩れないか？
🔍 使う変数
-
left：探索範囲の左端 -
right：探索範囲の右端（初期値：arr.length） -
mid： 探索範囲の中央
🔍 二分探索のイメージ
配列を「条件を満たす部分」と「満たさない部分」に分けたい。
🔍 そもそも「条件」とは？
二分探索で言う 条件 は「何を探したいか」によって決まる。
例：
arr = [1, 3, 5, 7, 9]
value = 4
やりたいこと：
「4 以上の値が出てくる最初の位置」を知りたい
→ これが 条件を満たす部分
-
arr[mid] < value→ 左側（条件を満たさない） -
arr[mid] >= value→ 右側（条件を満たす）
🔍 進み方の意味
1️⃣ left は 「条件を満たさない最後の位置の右隣」 を指す
2️⃣ right は 「条件を満たす最初の位置」 を指す
🔍 左右が一致したとき何が起きてる？
探索を繰り返すと：
- 左端
leftは「これ以下だと小さい」とわかっている場所の次を指す - 右端
rightは「これ以上だと条件を満たす」とわかっている場所を指す
最終的に left === right になると：
- 「これより左側は小さい」
- 「これ以上は条件を満たす」
これがまさに「境界線」だから、
left が value を入れるべき位置 になる。
🔍 例で確認！
// arr = [1, 3, 5, 7, 9]
// value = 4
// mid = Math.floor((left + right) / 2);
left = 0, right = 5
1) mid = 2 → arr[2] = 5
5 >= 4 → right = 2
// 中央の値の方が大きい → 条件を満たす → right = mid
// 探索の範囲の右端を狭く再設定して繰り返す↓
2) mid = 1 → arr[1] = 3
3 < 4 → left = 2
// 中央の値の方が小さい → 条件を満たさない → left = mid + 1
// while(left < right){...} left = right = 2 → 終了
→ 結果: left = right = 2
ここで分かること：
- index 2 より左 → 4 未満（1, 3）
- index 2 以上 → 4 以上（5, 7, 9）
だから 4 を index 2 に入れれば OK！
🗒️ メモ＆まとめ
- 探索範囲を
leftrightで管理 -
midで中央を調べて右か左か判断 - 左右が一致したらその位置が答え
-
spliceでその位置に挿入