# One Line Binary Search

**URL:** <https://boards.straightdope.com/t/one-line-binary-search/731611>\
**Category:** Factual Questions\
**Created:** [September 17, 2015, 11:13pm UTC](https://boards.straightdope.com/t/one-line-binary-search/731611 "2015-09-17T23:13:05Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\
**Post date:** [September 17, 2015, 11:13pm UTC](https://boards.straightdope.com/t/one-line-binary-search/731611/1 "2015-09-17T23:13:05Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Digital\_is\_the\_new\_Analog](https://avatars.discourse-cdn.com/v4/letter/d/a88e4f/32.png) [@Digital\_is\_the\_new\_Analog](https://boards.straightdope.com/u/Digital_is_the_new_Analog)\
**Post date:** [September 17, 2015, 11:50pm UTC](https://boards.straightdope.com/t/one-line-binary-search/731611/2 "2015-09-17T23:50:29Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [September 17, 2015, 11:59pm UTC](https://boards.straightdope.com/t/one-line-binary-search/731611/3 "2015-09-17T23:59:16Z")

</div>

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;