welcome, andB[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. :)