ページ番号を引数として取り、ページが属する章を表す一意の文字列を返す get_chapter という関数があります。たとえば、「The Story Continues」などです。本以外のページ番号を入力すると、空の文字列が返されます。
最初のページはページ 0 です。チャプターは連続したページのセットであり、特定のページは 1 つのチャプターにのみ属します。
各章のページ範囲を識別することができる、どのアルゴリズムをお勧めしますか? get_chapter を呼び出す必要がある回数についての見積もりはありますか?
get_chapter の呼び出しをできるだけ制限する必要があります。章は平均 50000 ページです。そして本は約3000万ページ！何章あるのか不明。
最初のページで章境界のリストを準備します。
low最初のページとhigh最後のページに設定します。
の場合get_chapter(low) == get_chapter(high)、その範囲内のすべてが同じ章にあることがわかり、さらに分割する必要はありません。
get_chapter(low) != get_chapter(high)との場合low + 1 == high、異なる章に隣接するページがあります。それは、新しい章が高いところから始まることを意味します。
get_chapter(low) != get_chapter(high)およびの場合low + 1 < high、範囲内に少なくとも 1 つの章の境界があります。中間のページを選択して範囲を分割し、両方の新しい範囲 (low:middle と middle:high)を再帰的に下降します。
境界を見つけたときにリストに追加し、常に下位の部分範囲を最初に再帰した場合は、完了です。それ以外の場合は、境界リストを並べ替えます。
実行時の複雑さはおよそ O(number_of_chapters * log_2(average_chapter_size)) であると思いますが、これは総括的な分析であり、完全な分析ではありません。
いくつかの考え：
最後のページで get_chapter を呼び出して、チャプターの数を確認します。
チャプターの平均サイズを計算し、各チャプターの推定中央値に対して get_chapter を呼び出します。
隣接する章間の二分探索を使用して、境界を見つけます。
ステップ 2 からの初期見積もりが 2 つの章にまたがる、または同じ大きな章に含まれる大きな章または小さな章に合わせて変更します。
呼び出しの平均数は、n + log2(s) のようなものです。ここで、n は章の数で、s は章のページの平均サイズです。