于是很显然的,i和k可以通过二分搜索找到.
但是这样会面临两个问题:1. 根据n的规模,每次二分都需要30次查询,同时搜索i和k会需要60次查询.2. j的值如何求解?
于是,当我们发现一次查询后的y有整数解时,我们可以根据x和y计算出k的值,k=x + y -1.
但考虑到上面说的少数情况,我们可以通过查询(? x+y-2 x+y-1)来判断,如果查询结果是1,那么k=x+y-1.如果查询结果是3,可能是x=j-1,因此我们再尝试一次即可.
于是我们就能判断x到底是在j-1左边,还是在j右边,还是x就是j或j-1.