binary search


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in ruby

Source Code

def binary_search(arr, target)
    if arr.length < 1
        return -1
    end

    middle = arr.length / 2
    middle_value = arr[middle]

    if middle_value > target
        binary_search(arr[0, middle], target)
    elsif middle_value < target
        v = binary_search(arr[(middle+1)..-1], target)
        v < 0 ? v : (v + middle + 1)
    else
        middle
    end
end
require './binary_search'

describe "#binary_search" do
  it "Test empty array" do
    binary_search([], 1).should eq(-1)
  end

  it "Search last key" do
    binary_search([1,2,3,4,5], 5).should eq(4)
  end

  it "Search first key" do
    binary_search([1,2,3,4,5], 1).should eq(0)
  end

  it "Search middle key" do
    binary_search([1,2,3,4,5], 3).should eq(2)
  end

  it "Search not found key" do
    binary_search([1,2,3,4,5], 10).should eq(-1)
  end
end