Skip to content

Instantly share code, notes, and snippets.

@amgando
Last active September 10, 2015 04:18
Show Gist options
  • Save amgando/0e1aea7a8757102ef279 to your computer and use it in GitHub Desktop.
Save amgando/0e1aea7a8757102ef279 to your computer and use it in GitHub Desktop.
class Window
SCALE = 100
class Collapsed < ArgumentError; end
attr_reader :low, :mid, :high, :max
def set(window)
# p "setting window to #{window}"
@low, @mid, @high = window
self
end
def init(size)
self.set [0, size / 2, size-1]
end
def lowside!
self.set [low, (low+mid)/2, mid-1]
end
def highside!
self.set [mid + 1, (mid+high)/2, high]
end
def empty?
low.nil? && mid.nil? && high.nil?
end
def collapsing?
low == mid || mid == high || low == high
end
def data
[low, mid, high]
end
alias_method :inspect, :data
def scale
@max ||= high
self.data.map{ |el| ((el.to_f / @max) * SCALE).to_i }
end
def render(line = ' ', target = nil)
markers = ['\\', '|', '/']
line_symbol = line
show = line_symbol * SCALE
self.scale.each_with_index do |data, idx|
show[data] = markers[idx]
end
show[target] = '*' unless target.nil?
show
end
alias_method :to_s, :render
end
def binary_search(needle, haystack, window = Window.new)
if window.empty?
window.init(haystack.length)
end
puts window
low, mid, high = window.data
if window.collapsing?
# scan the entire window for the needle
(window.data.min..window.data.max).each do |idx|
return idx if needle == haystack[idx]
end
# http://devblog.avdi.org/2014/05/21/jim-weirich-on-exceptions/
fail Window::Collapsed, "failed to find [#{needle}]!"
end
# found it
if needle == haystack[mid]
return mid
# now search low side
elsif needle < haystack[mid]
return binary_search(needle, haystack, window.lowside!)
# now search high side
elsif needle > haystack[mid]
return binary_search(needle, haystack, window.highside!)
end
end
# --------------------------------------------------------
SAMPLE_SIZE = 10000
COLLECTION_SIZE = 1000
h = (1..SAMPLE_SIZE).to_a.sample(COLLECTION_SIZE).sort
n = h.sample
# puts "haystack:\n#{h}\n\n"
puts "needle: #{n}\n"
puts "should find it at [#{h.index(n)}]"
puts "looking for #{n}. found it at #{binary_search(n, h)}"
$ ruby binary_search.rb
needle: 4440
should find it at [443]
\ | /
\ | /
\ | /
\ | /
\ | /
\ |/
\|/
\/
/
looking for 4440. found it at 443
Sherif Abushadi ~/Documents/code/dbc/phase-1/binary-search
$ ruby binary_search.rb
needle: 8029
should find it at [816]
\ | /
\ | /
\ | /
\ | /
\ | /
\| /
\/
/
looking for 8029. found it at 816
Sherif Abushadi ~/Documents/code/dbc/phase-1/binary-search
$ ruby binary_search.rb
needle: 1180
should find it at [120]
\ | /
\ | /
\ | /
\ | /
\ | /
\| /
\|/
\/
looking for 1180. found it at 120
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment