Skip to content

Instantly share code, notes, and snippets.

@robinator
Created October 23, 2010 22:40
Show Gist options
  • Save robinator/642786 to your computer and use it in GitHub Desktop.
Save robinator/642786 to your computer and use it in GitHub Desktop.
Binary search implemented in coffeescript.
binary_search = (val, L) ->
return false if L.length == 0
mid = Math.floor(L.length / 2)
if L[mid] == val
return mid
else if val > L[mid]
binary_search(val, L[(mid + 1)..(L.length)])
else
binary_search(val, L[0..(mid - 1)])
list = [1,2,3,4,5,6,7,8]
alert binary_search(18, list) # false
alert binary_search(3, list) # 2
alert binary_search(6, list) # 5
@Hengjie
Copy link

Hengjie commented Jun 20, 2013

Wouldn't line 5's return mid just constantly return 1?

Here's an example at each level:
Assume val = 2

  1. L.length = 9
    mid = floor ( 9 / 2 ) = 4
  2. L.length = 4
    mid = floor ( 4 / 2 ) = 2
  3. L.length = 2
    mid = floor ( 2 / 2 ) = 1
    if L[mid] == val matches and we now return 1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment