Skip to content

Instantly share code, notes, and snippets.

@mrmurphy
Created November 6, 2013 22:37
Show Gist options
  • Save mrmurphy/7345485 to your computer and use it in GitHub Desktop.
Save mrmurphy/7345485 to your computer and use it in GitHub Desktop.
Coffeescript Binary Search (By Ryan Shaw)
binaryFindClosest = (haystack, needle) ->
closestBelow = 0
closestAbove = haystack.length - 1
middle = Math.floor (closestBelow + closestAbove) / 2
while haystack[middle] isnt needle and closestBelow < closestAbove
if needle < haystack[middle]
closestAbove = middle - 1
else if needle > haystack[middle]
closestBelow = middle + 1
# recalculate middle
middle = Math.floor (closestAbove + closestBelow) / 2
deltaBelow = needle - closestBelow
deltaAbove = closestAbove - needle
if deltaBelow < deltaAbove
return direction: 'down', value: closestBelow, delta: deltaBelow
else
return direction: 'up', value: closestAbove, delta: deltaAbove
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment