algorithm - 给定函数 get_chapter(page_number) 建立书中的章节

Question

我有一个名为 get_chapter 的函数，它以页码作为参数并返回一个表示该页面所属章节的唯一字符串，例如“故事继续”。如果我在书外输入页码，则会返回一个空字符串。

第一页是第 0 页。章节是一组连续的页面，给定的页面只属于一个章节。

你会推荐什么算法来识别每一章的页面范围？关于我需要调用 get_chapter 多少次的任何估计？

我需要尽可能限制对 get_chapter 的调用。章节平均 50000 页。这本书大约有30000000页！不知道有多少章。

Answer 1

用第一页填写章节边界列表。

设置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，则范围内至少有一个章节边界。通过在中间选择一个页面来拆分范围并递归地降低两个新范围（低：中和中：高）。

如果您在找到边界时将边界添加到列表中，并且始终首先递归较低的子范围，那么您就完成了。否则，对边界列表进行排序。

我相信运行时复杂度大约为 O(number_of_chapters * log_2(average_chapter_size))，但这是一个直觉检查而不是彻底的分析。

Answer 2

一些想法：

1. 在最后一页调用 get_chapter 以查看有多少章。

2. 计算出一章的平均大小，并调用 get_chapter 来估计每章的中间部分。

3. 在相邻章节之间使用二分搜索来找到边界。

4. 针对第 2 步中的初始估计跨越两章或属于同一大章的大章或小章进行修改。

平均调用次数类似于 n + log2(s)，其中 n 是章节数，s 是章节的平均大小（以页为单位）。