binary search


See On Github

Data

Contributor

Generic placeholder thumbnail

by mitogh

in ruby

Source Code

def binary_search(haystack = [], needle = nil)
  return nil if needle.nil? || haystack.nil?
  lo = 0
  hi = haystack.size - 1
  while lo <= hi do
    mid = lo  + ((hi-lo) / 2 )
    return mid if haystack[mid] == needle
    (haystack[mid] < needle) ? (lo = mid + 1) : (hi = mid - 1)
  end
end
require './binary_search'

describe "#binary_search" do
  # A order array
  let(:array){ (1..100).to_a }

  context "Search in empty array" do
    it{ expect(binary_search([], 10)).to eq nil }
  end

  context "Search a not found needle in the haystack" do
    it{ expect(binary_search(array, 101)).to eq nil }
  end

  context "Search the first element" do
    it{ expect(binary_search(array, 1)).to eq 0 }
  end

  context "Search the middle element" do
    it{ expect(binary_search(array, 50)).to eq 49 }
  end

  context "Search the last element" do
    it{ expect(binary_search(array, 100)).to eq 99 }
  end

  context "Search without a needle" do
    it{ expect(binary_search(array)).to eq nil }
  end

  context "Search without a haystack" do 
    it{ expect(binary_search(nil,100)).to eq nil }
  end
end