Implemente el algoritmo de búsqueda binaria como se usa para identificar la revisión del código fuente que rompe un programa de software de computadora. Su herramienta debe tomar dos argumentos que especifiquen la revisión numerada más temprana y más reciente para buscar (ambos enteros positivos), y tiene dos opciones para hacer comparaciones:

1. Ejecute el comando de shell ./test N, donde N es el número de revisión. Si la prueba pasa ( es decir, la revisión es buena), devolverá el código de salida 0.

2. Llame a la función test(N), que volverá truesi la prueba pasa, de lo falsecontrario.

La salida estándar debe ser el número de la primera revisión incorrecta e intente hacer que el código fuente de su herramienta sea lo más breve posible. ¡Disfrutar!

Ruby - 92 82 62 60 caracteres

La iterativa es mucho más corta, pero no es tan fría como la cola recursiva.

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

El antiguo método recursivo de cola para referencia

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)]

Script de prueba

Utiliza un poco de magia para inyectar la testfunción y ejecuta un archivo que consiste únicamente en el código anterior.

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}`}"

Salida:

Using input:
  low=4
  high=75343785543465286986587973836706907796015092187720
  first_bad=5013102893257647460384884
Output: 5013102893257647460384884

Python, 64 caracteres

Este es recursivo, por lo que desbordará la pila para una entrada realmente grande

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

prueba de funcionamiento

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)

salidas

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66

Python - 77 caracteres

Abusar del módulo de bisección de python. L es el valor bajo, H es el valor alto

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

aquí hay una prueba de funcionamiento

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)

salidas

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

Explicación:

Así es como se define la bisección. Básicamente espera una lista y decide si bisecar hacia arriba o hacia abajo en función del valor que encuentra al mirar a[mid]. Este llamadas __getitem__en aque en lugar de ser una lista, es una clase que he definido mi mismo.

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

Python - 70 caracteres

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

prueba de funcionamiento

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)

salidas

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  63
testing  67
testing  65
testing  66
65