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