25

2019-07-27 17:28:21 +08:00 1

@solider245 就是一般意义上我们说的二分查找，一般的程序员应该都了解的。 如果你这方面有缺失，我时间不多，只能在这里简单解释一下：假设我有一个有序的整数数组，我想要查询里面一个数的下标，我先拿数组中间的数和目标数对比，如果相等那就找到了，如果小于目标值，就说明目标值在数组的后半部分，那我就去后半部分继续二分，如果大于目标值，说明目标值在数组的前半部分，我就去前部分用同样的方法找。

这样不断地分割数组，我只需要正比于数组长度的对数的时间就能找到值，也就是 1024 长度的数组我只需要找 10 次左右。

对于你的问题，你可以把所有页面看成是一个数组，合法是 0，不合法是 1，这个数组就是[0,0,0,....,1,1,1,1]这样的形式，你要找到最右边的 0，二分搜索就可以了。二分搜索的实现是很容易出 bug 的（除非你很好地掌握了循环不变式的思想， 但是如果你不知道二分搜索，我估计你也不知道循环不变式），所以不建议自己实现。bisect 标准模块已经实现了数组的二分搜索，所以你只需要构造这么一个数组，但是你不能真的去构造数组，不然相当于每个页面都去读取了一次，所以你可以覆盖__getitem__方法，构造一个假的数组，每次读数组的第 i 个值，你去取第 i 个页面就行了。

我给的代码只是简单的 demo，要达到工业强度，还需要一些改进，比如请求失败的处理之类的，祝好运。

PS：while 的做法是每个页码都尝试去读一次，比二分搜索慢了很多，但是如果你的性能需求没有你帖子里说的那么高，那就怎么简单怎么来吧。