Binary search ("bisect") tool

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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