建立書中的章節，賦予函數get_chapter（page_number）

Question

我有一個叫做get_chapter的函數，它將頁碼作爲參數並返回一個唯一的字符串，表示頁面所屬的章節，例如「The Story Continues 」。如果我在書外輸入頁碼，我會返回一個空字符串。

第一頁是第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 +的log 2（S），其中n爲章節和s的數量是在頁面的章節的平均規模。