https://bugs.openldap.org/show_bug.cgi?id=10526
--- Comment #8 from Howard Chu hyc@openldap.org --- It's not clear that using binary search is actually an optimization in the case of two lists. That requires a lot of setup, and in sparse lists usually a single cursor increment is sufficient. E.g. using your test harness, with span=50000, a couple test arrays:
gdb) p a $97 = {48, 561, 830, 1039, 1180, 1716, 3496, 4396, 4577, 4874, 5704, 7840, 8809, 10437, 11020, 15124, 17456, 20076, 21188, 21781, 23226, 23362, 23650, 26690, 27326, 27385, 28610, 29661, 30207, 30762, 30874, 31278, 31780, 32215, 32478, 33171, 37241, 37419, 39315, 39322, 39365, 44196, 44678, 45238, 45629, 46511, 46683, 49124, 49953, 49, 50, 48499, 49509, 49769, 0 <repeats 8138 times>, <unavailable> <repeats 191808 times>} (gdb) p b $98 = {80, 3510, 4309, 4837, 4963, 5017, 5480, 6087, 7795, 8513, 9549, 10012, 10161, 10427, 10484, 12562, 13007, 13753, 14185, 14857, 14919, 14933, 15161, 15523, 15600, 16057, 16303, 16565, 17792, 18627, 19088, 19949, 21731, 22354, 23500, 24359, 24462, 24913, 25042, 25441, 26714, 27242, 28034, 28079, 28380, 29309, 30223, 30793, 31023, 31532, 32511, 32790, 33513, 34047, 34591, 34815, 34945, 35191, 35357, 35510, 37063, 37821, 38216, 38632, 39696, 40963, 41642, 42080, 42263, 42808, 43331, 43891, 44125, 44286, 44347, 45799, 46183, 46451, 47121, 47836, 47950, 0 <repeats 8111 times>, <unavailable> <repeats 191808 times>}
The values typically leapfrog each other, and one or two cursor increments is sufficient to get to the next candidate.