two_missed_values.js

findMissedValues = (arr) ->
  result = []
  findWithBinarySearch result, arr, 0, arr.length - 1
  result
 
findWithBinarySearch = (result, arr, from, to) ->
  from = to if from > to
  if (from == to && arr[to] != to)
    diffPosition = arr[to] - to - 1
    diffNeighbor = if diffPosition == 0
      sign = 1
      arr[to+1] - arr[to] - 1
    else
      sign = -1
      arr[to] - arr[to-1] - 1
    
    for i in [1..diffNeighbor]
      result.push arr[to] + i * sign
  
  else
    middle = getMiddle from, to
    margin = arr[middle] - middle - 1
      
    searchLeft  = findWithBinarySearch.bind null, result, arr, from, middle - 1
    searchRight = findWithBinarySearch.bind null, result, arr, middle + 1, to
        
   switch margin
    when 0 then do searchRight
    when 2 then do searchLeft
    when 1
      do searchLeft
      do searchRight
            
getMiddle = (from, to) ->
  from + Math.ceil((to - from) / 2)

#
# Tests
#

tests = [
  { value: [1,2,4,5,7,8], expect: [3,6] }
  { value: [1,3,5,6,7,8], expect: [2,4] }
  { value: [1,2,3,6,7,8], expect: [4,5] }
  { value: [1,2,3,4,5,8], expect: [6,7] }
  { value: [1,4],         expect: [2,3] }
]

checkArraysEquality = (first, second) ->
  (first.length == second.length) && first.every (element, index) ->
    return element == second[index]

tests.forEach (test) ->
  result = findMissedValues test.value
  console.log '========test========'
  console.log "argument: #{test.value}"
  console.log "given: #{result}"
  console.log "expected: #{test.expect}"
  console.log "passed: #{checkArraysEquality result, test.expect}"
  console.log '=======/test========'
  console.log '\n'