# Challenge

Implement binary search on a list of length 256 with no branches.

# Specification

• Input an integer X and a strictly increasing list of integers
• Output is the greatest element of the list that is less than or equal to X
• The output will always exist
• List will always have exactly 256 elements and be strictly increasing
• The algorithm must be a binary search on the list

# Example code (with branches)

Without branches, these examples would be valid entries.

First a functional example (actually valid Haskell code):

b value list = b' 0 7
where
b' pos bitpos | bitpos < 0                          = list !! pos
| (list !! (pos + 2^bitpos)) <  value = b' (pos + 2^bitpos) (bitpos - 1)
| (list !! (pos + 2^bitpos)) == value = list !! (pos + 2^bitpos)
| otherwise                           = b' pos (bitpos - 1)


Now a pseudocode iterative example:

b(value, list):
pos = 0
bitpos = 7
while bitpos >= 0:
if list[pos + 2^bitpos] < value
pos    += 2^bitpos
elseif list[pos + 2^bitpos] == value
return list[pos + 2^bitpos]
bitpos -= 1
return list[pos]


# Rules

• Branches include: if/then, switch, case, for, while, ?:, guards, and all other branches
• Instead of a list, you may use a list-like object, so space separated string, vector, etc.
• Entry may be a function or full program
• If your language has a function that solves this challenge, it is not allowed
• Score is in bytes, lowest score wins!

# Example Input/Output (abbreviated)

Input:  50, [..21,34,55,89,144..]
Output: 34

Input:  15, [..2,3,15,25,34,35..]
Output: 15

Input:  144, [..37,50,65,82,101,122,145..]
Output: 122

• Maybe separating the specifications from the rules would make it clearer for those who closed it? – user81655 Feb 19 '16 at 5:11
• @user81655 Good suggestion. I also added examples and the algorithm in two forms. Do you think I should add a worked example? – Michael Klein Feb 19 '16 at 6:18
• Personally I think it's very clear as it is now. The test cases really help. – user81655 Feb 19 '16 at 6:44
• @user81655 Great, now I just have to wait – Michael Klein Feb 19 '16 at 6:46
• Might as well just leave this here for reference. – Michael Klein Mar 11 '16 at 3:06

# C, 75 bytes

Here's the code:

#define g p+=(x>=p[i/=2])*i
b(x,p,i)int*p;{i=256;g;g;g;g;g;g;g;g;return*p;}


Less golfed:

int bin_search(int x, int * p){
int i = 256;
i = i / 2;
p += (p[i] <= x) * i;
\\ above two lines repeated 8 times
return *p;
}

• Noncompeting why? – CalculatorFeline Mar 11 '16 at 4:35
• @CatsAreFluffy I'll edit, I just accepted my own answer because it didn't look like anyone else was going to answer. If you want to post an answer, I'll reopen. – Michael Klein Mar 11 '16 at 4:44