Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Binary search gem
# -*- encoding: utf-8 -*-
$:.unshift '.'
require 'bsearch'
Gem::Specification.new do |s|
s.name = 'bsearch-ruby'
s.version = BSearch::VERSION
s.authors = ["Aaron Suggs"]
s.description = "A binary search implementation in ruby"
s.email = "aaron@ktheory.com"
s.files = ['bsearch.rb']
s.require_path = '.'
s.homepage = 'https://gist.github.com/3219940'
s.rdoc_options = ["--charset=UTF-8"]
s.summary = %q{Binary search}
s.test_files = ['test_bsearch.rb']
s.required_ruby_version = '>= 1.9.3' # Maybe less?
end
# Binary search algorithm
module BSearch
VERSION = '0.1.1'
# Assume's haystack is an array of comparable objects
def self.bsearch(needle, haystack, first=0, last=nil)
last ||= haystack.size - 1
return nil if last < first # not found, or empty haystack
cur = first + (last - first)/2
case needle <=> haystack[cur]
when -1 # needle is smaller than cur value
bsearch(needle, haystack, first, cur-1)
when 1 # needle is larger than cur value
bsearch(needle, haystack, cur+1, last)
when 0
cur
end
end
end
require 'test/unit'
require_relative 'bsearch'
class BSearchTest < Test::Unit::TestCase
def test_bsearch_results
ary = (0..9).to_a
ary.each do |i|
assert_equal i, BSearch.bsearch(i, ary)
end
end
def test_empty_haystack
assert_nil BSearch.bsearch(0, [])
end
def test_not_found
needles = [1,3,5,7]
haystack = [2,4,6]
needles.each{|n| assert_nil BSearch.bsearch(n, haystack) }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment