Implement binary search on a list of length 256 with no branches.
- Input an integer
Xand a strictly increasing list of integers
- Output is the greatest element of the list that is less than or equal to
- 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]
- Branches include:
?:, 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