[karolkozub]

  The following values were inspected:
  1
  2
  4
  8
  16
  32
  64
  32
  48
  40
  44
  42
  43

The most surprising part for me is that in the integer search 32 is inspected twice. From my brief testing it seems to only happen with infinite ranges. Is that a bug in bsearch or am I missing something?

[progval]

With a finite range, you can bisect directly by splitting in the middle of the range.

With infinite ranges, you can't do that; so the usual way is to start with a small number and increase exponentially until you find a number that is too large; which is what is done here. When you got that number, it becomes the upper bound of a finite interval.

So that's a two step process, which we can see here. The first 32 is in the exponential growth step (so is 64), and the second one is in the bisect step.

This will always happen exactly once (unless the expected result is 0) and for only the first pivot in the bisect, so it's not that bad; but indeed, they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step.

[MauranKilom]

> they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step.

Did you mean [n/2; n]?

[progval]

Oops, yes, I did.

[ashtonkem]

Interestingly, they're doing unnecessary work here. In this case, the algorithm has already checked 32, so there's no need to check again.

In fact, if you're checking N, it's guaranteed that N/2 has already been checked, and the next best step should be (3/4)N; in this case 48.

[lifthrasiir]

It shouldn't be a problem but technically you are right that Ruby does one more comparison than needed. My guess is that it would mean to keep the previous value of mid (as in `bsearch_integer_range(prev_mid, mid, 0)` instead of the current `bsearch_integer_range(beg, mid, 0)`) and that might be annoying to do in C.