One Line Binary Search

Factual Questions
1

I would swear that, at one point in the past, I encountered someone’s personal version of a binary search algorithm, which consisted - if I remember correctly - entirely of a for loop and a single statement. E.g.:

for (something) something;

It could have been:

for (something) if (something) return something;

But certainly it looked reasonable to declare a one-liner, even if it might be more nicely laid out on 2 or 3 lines. Still far smaller than most implementations.

There was no recursion, it wasn’t using any operator overloads, macros, or other nonsense. It was just a straightforward binary search (e.g., over an array of ints).

Anyone aware of it? I don’t think it was widely quoted or used. I just found it in a discussion of binary searches.

2

I’m not in a programming mind set right now (tough day at the office…Momma said there’d be days like this…)… but I could imagine something like:

for (i = m/2, range = m/2; target != a*; ; ) if (target < a*) {i = i - range/2; range = range / 2} else {i = i + range / 2; range = range / 2}

That’s pretty sloppy, and there are lots of edge conditions that I’m not handling…but does it seem like the type of thing you are remembering?

3

Another, similar one (also written without thinking too hard about edge cases and the like):

for (i=N/2, l=0, r=N-1; l <= r; i=(l+r)/2) if (x < a*) r = i-1; else if (x > a*) l = i+1; else break;