Skip to content

Instantly share code, notes, and snippets.

@sumanmukherjee03
Last active December 17, 2015 17:19
Show Gist options
  • Save sumanmukherjee03/5645431 to your computer and use it in GitHub Desktop.
Save sumanmukherjee03/5645431 to your computer and use it in GitHub Desktop.
Extend the array class with merge_sort and binary_search
require 'rspec'
RSpec.configure do |config|
config.mock_with :rspec
config.color_enabled = true
end
module ArrayExt
def merge_sort
if self.length <= 1
self
else
middle = self.length / 2
left = self[0...middle].merge_sort
right = self[middle...(self.length)].merge_sort
merge(left, right)
end
end
def binary_search(value, from = 0, to = self.length)
middle = from + (to - from) / 2
if self[middle] == value
middle
elsif to - from == 1
nil
elsif self[middle] < value
self.binary_search(value, middle, to)
else
self.binary_search(value, from, middle)
end
end
private
def merge(left, right)
result = []
left_copy = left.dup
right_copy = right.dup
while(left_copy.length * right_copy.length > 0) do
if left_copy.first < right_copy.first
result << left_copy.shift
else
result << right_copy.shift
end
end
result + left_copy + right_copy
end
end
class Array
include ArrayExt
end
describe "ArrayExt" do
subject { [7, 3, 6, 1, 9, 4] }
describe "#merge_sort" do
it "sorts the array" do
subject.merge_sort.should eq([1, 3, 4, 6, 7, 9])
end
end
describe "#binary_search" do
subject(:sorted_array){ [1, 3, 4, 6, 7, 9] }
it "returns the element position you are searching for" do
sorted_array.binary_search(7).should eq(4)
end
it "returns nil if element is not found" do
sorted_array.binary_search(8).should be_nil
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment