8
\$\begingroup\$

Implement the binary search algorithm as used to identify the source code revision that breaks a computer software program. Your tool should take two arguments specifying the earliest and latest numbered revision to search (both positive integers), and you have two options for making comparisons:

  1. Execute the shell command ./test N, where N is the revision number. If the test passes (i.e. the revision is good), it will return exit code 0.

  2. Call the function test(N), which will return true if the test passes, false otherwise.

Standard output must be the number of the first bad revision, and try to make your tool's source code as short as possible. Enjoy!

\$\endgroup\$
  • \$\begingroup\$ Just some clarification, do you want a script or just a function? \$\endgroup\$ – Nemo157 Feb 1 '11 at 6:47
  • \$\begingroup\$ @Nemo157: A complete script. I include the test(N) function option primarily for fairness to those programming languages with no standard way to execute shell commands, such as JavaScript. \$\endgroup\$ – PleaseStand Feb 1 '11 at 12:24
4
\$\begingroup\$

Ruby - 92 82 62 60 characters

Iterative is way shorter, but nowhere near as cool as tail recursive.

l,h=$*.map &:to_i
test(m=(l+h)/2)?l=m+1:h=m-1 while l<=h
p l

The old tail recursive method for reference

b=proc{|l,h|h<l ?l:(m=(l+h)/2;test(m)?l=m+1:h=m-1;redo)}
puts b[*$*.map(&:to_i)]

Testing script

Uses a little magic to inject the test function and runs a file consisting of purely the above code.

low = Random.rand(100)
mid = low + Random.rand(1e25)
high = mid + Random.rand(1e50)

File.open('./bisect-test-method.rb','w') do |file|
  file << "def test(value)
             value < #{mid}
           end
          "
end

puts "Using input:"
puts "  low=#{low}"
puts "  high=#{high}"
puts "  first_bad=#{mid}"
puts "Output: #{`ruby -r ./bisect-test-method golf-bisect.rb #{low} #{high}`}"

Output:

Using input:
  low=4
  high=75343785543465286986587973836706907796015092187720
  first_bad=5013102893257647460384884
Output: 5013102893257647460384884
\$\endgroup\$
5
\$\begingroup\$

Python, 64 chars

This one is recursive, so will overflow the stack for really large input

01234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |
 B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

test run

def test(n):
    print "testing ", n
    return n<66

L,H=10,1000


B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

print B(L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66
\$\endgroup\$
  • \$\begingroup\$ Should print 66, not 65 (return H, not L). \$\endgroup\$ – Keith Randall Feb 1 '11 at 5:04
  • \$\begingroup\$ @Keith, ok changed that \$\endgroup\$ – gnibbler Feb 1 '11 at 5:19
2
\$\begingroup\$

Python - 77 chars

Abusing the python bisect module. L is the low value, H is the high value

class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

here is a test run

def test(n):
    print "testing ", n
    return n>66
L,H=10,1000

class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  56
testing  64
testing  68
testing  66
testing  67

Explanation:

Here is how bisect is defined. Basically it expects a list and decides whether to bisect up or down based on the value it finds by looking at a[mid]. This calls __getitem__ on a, which instead of being a list, is a class that I have defined myself.

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect=bisect_right
\$\endgroup\$
2
\$\begingroup\$

Python - 70 chars

def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

test run

def test(n):
    print "testing ", n
    return n<66
L,H=10,1000

def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

print B(L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  63
testing  67
testing  65
testing  66
65
\$\endgroup\$

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.