背景
達人プログラマーを読んでいます。
二分探索法について触れられていたのでコードを書いたり、深掘りしてみます。
二分探索法の処理の流れ
- 配列の中央値を取得する
- 中央値が探している値と
2.a. 等しいなら終了する
2.b. 探している値より
2.b'. 大きい場合は配列の前半を探索範囲にし、1から探索し直す
2.b''. 小さい場合は配列の後半を探索範囲にし、1から探索し直す
これをコードにしたものが以下です。
業務でTypeScriptとGoを使っているのでそれぞれ書いてみます。
const binarySearch = (arr: number[], target: number): number => {
const sortedArr = arr.sort((a, b) => a - b);
/** 配列の中央のindex */
const medianIndex = Math.floor(sortedArr.length / 2);
const medianValue = sortedArr[medianIndex];
/** 中央の値がターゲットと一致する場合 */
if (medianValue === target) {
return medianIndex;
}
/** 中央の値がターゲットより大きい場合 */
if (medianValue > target) {
return binarySearch(sortedArr.slice(0, medianIndex), target);
}
/** 中央の値がターゲットより小さい場合 */
if (medianValue < target) {
return binarySearch(sortedArr.slice(medianIndex + 1), target) + medianIndex + 1;
}
/** ターゲットが見つからない場合 */
return -1;
}
import "sort"
func binarySearch(arr []int, target int) int {
sortedArr := arr
sort.Ints(sortedArr)
medianIndex := len(sortedArr) / 2
medianValue := sortedArr[medianIndex]
if target == medianValue {
return medianIndex
}
if target < medianValue {
return binarySearch(sortedArr[:medianIndex], target)
}
if target > medianValue {
return binarySearch(sortedArr[medianIndex+1:], target) + medianIndex + 1
}
return -1 // Target not found
}
二分探索の計算量
計算量はO(logN)となっていて、順番に探索する線形探索のO(N)よりもコストが低いです。
二分探索をデバッグに応用する
本では以下三つのケースで有効だと紹介していました。
- エラーのスタックトレース内でどの処理でエラーが起きたか特定する時
- バグが見つかった際にどのバージョンで起こったかを特定する時
- 複数のデータの中からどのデータを使うとエラーが起こるか特定する時
知らず知らずのうちに実はやっていたこともあるので、これが二分探索だったのかと理解しました。
二分探索は他にも応用できることがあるのか
フロントエンド、UIの応用例を一つ紹介します。
テキストの自動リサイズ（最大フォントサイズの探索）
目的：テキストがコンテナにちょうど収まる最大フォントサイズを計算
二分探索でフォントサイズを大きくしながら、オーバーフローしない最大値を探す
function findMaxFontSize(text, container) {
let min = 1;
let max = 100;
let best = 1;
while (min <= max) {
let mid = Math.floor((min + max) / 2);
container.style.fontSize = `${mid}px`;
container.innerText = text;
if (container.scrollWidth <= container.clientWidth && container.scrollHeight <= container.clientHeight) {
best = mid;
min = mid + 1;
} else {
max = mid - 1;
}
}
return best;
}
こちらの条件文について説明します。
container.scrollWidth <= container.clientWidth &&
container.scrollHeight <= container.clientHeight
scrollWidth,clientWidth,scrollHeight,clientHeightについての説明は以下です。
| プロパティ名 | 意味 | 含まれる要素 | 主な用途 |
|---|---|---|---|
| scrollWidth | 要素内コンテンツの「全体の幅」 |
padding含むが、はみ出し分も含む
|
横スクロールの必要有無を調べる |
| clientWidth | 見えている範囲の「幅」 |
paddingまで含む（スクロールバーは除く） |
表示領域の幅を知る |
| scrollHeight | 要素内コンテンツの「全体の高さ」 |
padding含むが、はみ出し分も含む
|
縦スクロールの必要有無を調べる |
| clientHeight | 見えている範囲の「高さ」 |
paddingまで含む（スクロールバーは除く） |
表示領域の高さを知る |
つまり、上の条件文は
テキストや画像などが、ぴったり表示領域内に収まっていることを示しています。
具体例（ビジュアルイメージ）
小さいテキストを表示：
scrollWidth < clientWidth → はみ出してない
✅ → OK
大きなテキストで改行も多い：
scrollHeight > clientHeight → はみ出している
❌ → フォントサイズを下げる必要あり
最後に
本で学んだことを自分なりに深掘りして理解を深めたいです。
二分探索を使うシーンがあるかアンテナを貼りたいと思いました。
Discussion