Created
December 21, 2017 19:20
-
-
Save danman01/fcb74a041864ac2733e59dd93c7e6a62 to your computer and use it in GitHub Desktop.
binary_search_ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
# Usage: ruby binary_search.rb [debug] 50 0 100 | |
# Returns: [optional: count of tries] @item, when found within first and last (not inlusive) | |
module Algorithms | |
class BinarySearch | |
def initialize | |
@n = 0 | |
@debug = ARGV.slice!(0) if ARGV[0] == "debug" | |
@item = ARGV[0].to_i | |
@first = ARGV[1].to_i | |
@last = ARGV[2].to_i | |
end | |
def binarySearch(arr = (@first..@last).to_a, item = @item, first = @first, last = @last) | |
if (!last) then last = arr.length end | |
if @debug | |
puts " try #{@n} " | |
@n += 1 | |
end | |
midpoint = (last - first) / 2 + first | |
if (arr[midpoint] == item) then return midpoint end | |
if (arr[midpoint] > item) then return binarySearch(arr, item, first, midpoint) end | |
if (arr[midpoint] < item) then return binarySearch(arr, item, midpoint, last) end | |
end | |
end | |
end | |
puts Algorithms::BinarySearch.new.binarySearch |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment