JavaScript の 二分探索の実装

レベル 5421 打鍵

binarySearch はソート済み配列の中央の要素を調べ、探索範囲を毎回半分にして値を探す。7 では 3、存在しない 8 では -1、1 では 0 を表示する。

JavaScript のコード

// ソート済み配列 arr 内の target の添字を返し、なければ -1 を返す
1function binarySearch(arr, target) {
// 探索範囲は最初、配列全体(添字0から length - 1 まで)
2 let left = 0;
3 let right = arr.length - 1;
4
// 範囲に要素が1つ以上残っている間、繰り返す
5 while (left <= right) {
// 中央の要素の添字(小数点以下は切り捨て)
6 const mid = Math.floor((left + right) / 2);
7
// 中央の要素が target なら、その添字を返す
8 if (arr[mid] === target) return mid;
// 中央の値が小さすぎるので、target は右半分にしかない
9 if (arr[mid] < target) left = mid + 1;
// 中央の値が大きすぎるので、左半分で探索を続ける
10 else right = mid - 1;
11 }
12
// 範囲が空になったので、target は配列にない
13 return -1;
14}
15
// 二分探索はこのようなソート済みの配列でしか使えない
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 は最初の中央(添字3)で見つかるので 3 を表示する
17console.log(binarySearch(sorted, 7));
// 8 は配列にないので -1 を表示する
18console.log(binarySearch(sorted, 8));
// 1 は先頭の要素なので 0 を表示する
19console.log(binarySearch(sorted, 1));

実行結果

3
-1
0
このコードでタイピング練習する

このコードでタイピング練習ができます。記録はランキングに反映されません。

このコードで使う記号

この JavaScript のコードで打つ記号と、出てくる回数です。

  • (× 12
  • )× 12
  • ,× 11
  • ;× 11
  • =× 10
  • .× 5
  • -× 3
  • [× 3
  • ]× 3
  • {× 2

JavaScript のレベル 5 のほかのコード例

← JavaScript タイピング練習のトップへ