B[i] records the A's interval ID(the index, not the real value).
and B's size is not necesarily to be 64, say, can be 200.
if B[i]=B[i+1], then B[i] is the value u want.
otherwise B[i+1]>B[i], you may just sub-divide the range [i/64, (i+1)/64).
Otherwise, you can just do a liear scan from A[B[i]] to A[B[i+1]],
the expect number of intervals tp be scanned
should be very small (O(1)). The worst case can be large as larger as
A's size (you can do a binary search again (O(lgn)),
but the overhead will be large).
Yup, A is random and sorted in increasing order?!, if u want to find
the right interval by comparison, the worst case bound is O(lgn), and
hard to improve. :)
－