Finds the last 0 in an array containing an arbitrary number of zeros followed by an arbitrary number of ones

findLastZero.coffee

# Finds the last 0 in an array containing
# an arbitrary number of zeros followed by an
# arbitrary number of ones.
# Uses a modified binary search, which is both
# simplified and caters for finding the very
# last instance of zero rather than just
# the first one found.

findLastZero = (arrayOfZeroesFollowedByOnes) ->

  start = 0
  stop  = arrayOfZeroesFollowedByOnes.length - 1
  
  if arrayOfZeroesFollowedByOnes[start] != 0
     return -1

  if arrayOfZeroesFollowedByOnes[stop] == 0
     return stop

  # since we round the pivot to the floor, we
  # always end up start and pivot coinciding
  while start != (pivot = Math.floor (start + stop) / 2)

    valueAtPivot = arrayOfZeroesFollowedByOnes[pivot]

    if valueAtPivot == 0
      # bring forward the start since there are still
      # zeroes at the pivot
      start = pivot
    else
      # bring backwards the stop since there is already
      # a one at the pivot
      stop = pivot

  start

## some testing ///////////////////////////////////////////////

testWithEachSequenceMaxLength = (max) ->
  numberOfZeroes = Math.floor(Math.random() * max)
  zeroes = Array.apply(null, Array(numberOfZeroes)).map(() -> 0)

  numberOfOnes = Math.floor(Math.random() * max)
  ones = Array.apply(null, Array(numberOfOnes)).map(() -> 1)

  finalArray = zeroes.concat ones
  console.log "array " + finalArray

  result = findLastZero finalArray

  if result != numberOfZeroes - 1
    alert: "something wrong with " + numberOfZeroes + " zeroes and " + numberOfOnes + " ones. Got "  + result + " should have been " + (numberOfZeroes - 1)
  #else
  #  alert "OK"

# Test the function.

for i in [1...1000]
  console.log "testing " + i + " with length 0"
  testWithEachSequenceMaxLength 0

for i in [1...1000]
  console.log "testing " + i + " with length 1"
  testWithEachSequenceMaxLength 1

for i in [1...1000]
  console.log "testing " + i + " with length 2"
  testWithEachSequenceMaxLength 2

for i in [1...1000]
  console.log "testing " + i + " with length 3"
  testWithEachSequenceMaxLength 3

# this make take 10 seconds
for i in [1...1000]
  console.log "testing " + i + " with length 10"
  testWithEachSequenceMaxLength 10

# this make take 10 seconds
for i in [1...1000]
  console.log "testing " + i + " with length 100"
  testWithEachSequenceMaxLength 100

alert "done, seems OK"