c++ - 在 C/C++ 中使用二进制搜索在日志文件中搜索日期时间

Question

我有一些log4cpp格式的日志文件

--根据log4cpp的性质，这个文件在每一行的开头是按照日期时间排序的

假设格式是这样的

2012-09-02 17:17:36.891 This is line 1 in file 2   
...
2013-08-05 14:17:35.344 This is line 607082 in file 2
2013-08-05 14:17:36.891 This is line 607083 in file 2
...
2013-09-05 14:27:36.891 This is line 934594 in file 2

现在我正在编写一个程序来解析这些文件并尝试快速定位到一行。

例如，如果我运行

./my_program -start_time "2013-08-05 14:17:36"file_2.txt

我希望这个程序可以返回 607083 作为结果。

此外，-start_time 可以基于其他粒度，例如“2013-08-05 14:17:35.899”或“2013-08-15”，但我期待最接近的结果。

我可以逐行遍历这个文件，并在每一行的开头比较时间戳(只需使用字符串比较)，但需要 O(N) 时间。我已经实现了它并发现如果在开始时跳过数百万行它真的很慢。

我想知道我们是否可以为此使用二进制搜索。我认为这是返回最近结果的最佳方式，并且只需要 O(lgN) 时间

Answer 1

是的，你可以。这是按日期排序的日志。为什么不取第一行和最后一行，它们应该是最近的和最近的最后一个日期。

您可以制作一个将日期转换为秒数的函数。在第一次调用时，转到日志的中间并检查你的日期是更大还是更小等等......(二进制搜索)

希望这会有所帮助，并希望我对这将如何工作的解释清楚