前置き
プログラミングについて勉強していくとアルゴリズムのカテゴリに触れることがあるかと思います。その時に大体のケースでソートや、全探索、二分探索について学ぶ方が多いのではないかと思います。しかしながら、実際にフロント側の開発（筆者はiOSアプリ開発ですが）ではこれらのアルゴリズムを使うケースはあまりないのではないかと思っています（筆者の経験では、、、）。ですが最近開発で二分探索を使う機会がありましたので共有できればとおもいます。
二分探索
二分探索（Binary Search）は、ソート済みのリストや配列内で指定した値を効率的に探すアルゴリズムです。大まかな手順は次の通りです。
- リストの中央にある要素を調べます。
- その要素が目的の値と一致すれば、探索はそこで終了します。
- 中央の要素が目的の値より大きければ、その要素より小さい方（左半分）を新たな探索範囲とします。
- 中央の要素が目的の値より小さければ、その要素より大きい方（右半分）を新たな探索範囲とします。
- 新たな探索範囲でステップ1から再び探索を行います。これを範囲がなくなるまで（目的の値が見つからない場合）または目的の値を見つけるまで繰り返します。
func binarySearch<T: Comparable>(_ array: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
return nil
} else {
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
if array[midIndex] > key {
return binarySearch(array, key: key, range: range.lowerBound ..< midIndex)
} else if array[midIndex] < key {
return binarySearch(array, key: key, range: midIndex + 1 ..< range.upperBound)
} else {
return midIndex
}
}
}
このように二分探索が機能する理由は、リストがすでにソートされているため、各ステップでリストの半分を無視できるからです。つまり、探索する範囲が毎回半分になります。これが二分探索がログ時間（つまり、O(logn)）で実行でき高速な理由です。
適用例
最近二分探索を使う必要がでてきた理由として以下のような要件がありました。
- TableViewをつかってAPIから取得した情報をリスト表示
- 表示するCellにはLabelがあり、そこにタイトルや情報などを表示
- 特定のLabelについて文末に特定の画像（添付動画では⭐️にしています）をいれたい。
- 特定のLabelについては指定行表示（添付動画では２行としています）までとしてそれ以上長くなる場合は...とする（文末の特定画像は...のあとに表示）
また、Cellが表示されるタイミングで文字列の計算を以下のようにします。
- 対象の文字列に画像を挿入
- 決められた幅に対して文字列の高さを計算
- 2.で計算した値を１行の高さで割って、行数を計算
- 3の結果、3行以上だったら文字列を短くして1にもどる。
上記のの要件を満たすためにはUILabelの制限を超えるため、表示したい文字列の長さを自分で計算する必要がありました。しかし、上記の計算ステップの4で単純に１文字づつ文字列を短くしていくと計算量がO(n)となり、大量の文字列に対する操作となるとパフォーマンスに影響を与えます。そこで二分探索を導入し、計算量をO(logn)に抑えることで、パフォーマンスの問題を解決しました。
動画ではCellに表示する文字は500文字でかつCellは最大で600表示するようになっています。
・愚直に１文字づつ消した場合
・二分探索を使った場合
結果的に、特に高速スクロールなどで大量のCellを生成する際や、大量の文字列を処理する必要がある時、アプリケーションのレスポンスを保つためのキーとなりました。二分探索の導入により、ユーザーエクスペリエンスが大幅に向上しました。
結論として、アルゴリズムの選択はアプリケーションの性能を大幅に左右します。今回の例では、二分探索を使用することで計算効率を大幅に改善し、結果的に良いユーザーエクスペリエンスを提供することができました。このようなアプローチは、他のアルゴリズムでも同様に適用可能で、適切なアルゴリズムを選択することでアプリケーションのパフォーマンスを向上させることが可能です。