binary_search.coffee

@iterative = (arr, key) ->
  low = 0
  high = arr.length - 1

  while high >= low
    mid = Math.floor (low + high) / 2
    return mid if arr[mid] == key

    if arr[mid] < key
      low = mid + 1
    else
      high = mid - 1
  null

@deferred_iterative = (arr, key) ->
  low = 0
  high = arr.length - 1

  while high > low
    mid = Math.floor (low + high) / 2

    if arr[mid] < key
      low = mid + 1
    else
      high = mid

  if high is low and arr[low] is key then low else null

@recursive = (arr, key, low, high) ->
  low ?= 0
  high ?= arr.length - 1

  return null if high < low

  mid = Math.floor (low + high) / 2

  if key > arr[mid]
    @recursive arr, key, mid + 1, high
  else if key < arr[mid]
    @recursive arr, key, low, mid
  else
    mid

binary_search.spec.coffee

binary_search = require __dirname + "/binary_search"

# TODO: Add full test cases from http://www.mac-guyver.com/switham/2010/04/Binary_Search/

describe 'binary search', ->
  array = [
    0,  0, 1, 1, 2,
    2, 3, 3, 7, 8,
    10, 11, 12, 13, 13,
    13, 14, 16, 16, 20,
    21, 22, 23, 24, 25,
    27, 28, 29, 29, 30,
    31, 32, 32, 35, 39,
    40, 40, 40, 42, 42,
    42, 44, 44, 45, 45,
    46, 47, 48, 48, 48,
    49, 50, 51, 54, 54,
    55, 55, 56, 56, 58,
    60, 62, 63, 64, 66,
    67, 68, 68, 70, 71,
    72, 72, 75, 76, 76,
    78, 78, 78, 79, 79,
    80, 81, 82, 85, 85,
    86, 87, 89, 89, 89,
    90, 95, 95, 95, 96,
    96, 96, 97, 97, 99,
    99, 99, 100, 105, 105,
    106, 107, 109, 110, 110,
    110, 111, 112, 113, 115,
    116, 116, 116
  ]

  for name, fn of binary_search
    describe name, ->
      it 'returns the correct indexes for each key', ->
        for item in array
          expect(fn(array, item)).toEqual array.indexOf(item)

      it 'returns null if the key is not in the array', ->
        expect(fn(array, -1)).toEqual null
        expect(fn(array, 117)).toEqual null