Binary search ("bisect") tool

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

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

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