-2
\$\begingroup\$

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

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;
}
\$\endgroup\$
  • \$\begingroup\$ Noncompeting why? \$\endgroup\$ – CalculatorFeline Mar 11 '16 at 4:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Michael Klein Mar 11 '16 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.