とりあえず二分探索する
二分探索で我慢できなくて配列aの最大値が数万くらいなら配列を展開する

int[] a = {1, 6, 9};
int[] b = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2}

配列aの最大値が24万程度なら、展開した配列bに必要なメモリは2^(18+2)で1MB弱