Binary search worst case

binsearch.coffee

binsearch = (a, t, probe) ->
  min = 0
  max = a.length - 1

  while (min <= max)
    i = Math.floor((min + max) / 2)
    v = a[i]

    probe? i, v

    if v is t
      return i
    else if v < t
      min = i + 1
    else
      max = i - 1

  return -1

review = (n, probe) ->
  a = mka(n)

  theoC = Math.ceil(Math.log2(a.length + 1))

  worstC = 0
  for v in a
    do (v) ->
      c = 0
      i = binsearch(a, v, -> c++)
      worstC = Math.max(c, worstC)

  probe? theoC, worstC
  if worstC isnt theoC
    console.log "Theoretical worst case #{theoC} disagrees with imperative worst case #{worstC} for n #{n}"

mka = (n) ->
  a = []
  if n > 0
    a.push(i) for i in [1..n]
  a

review(n) for n in [0..1024]

# The two answers that Khan Academy got wrong:
review(n, (theoC, worstC) -> console.log n, theoC, worstC) for n in [193, 1580000]