binary search

gistfile1.rb

# require 'benchmark'
# # ==> true

# def ascending?(data, opts={})
#   return false if data.nil?
#   (data.size-1).times do |i|
#     if block_given?
#       return false if yield(data[i]) > yield(data[i+1])
#     else
#       return false if data[i] > data[i+1]
#     end
#   end
#   return true
# end
# # ==> nil

# ascending? []
# # ==> true
# ascending? (1..1000000).to_a
# # ==> true
# ascending? [1,2,3,2]
# # ==> false

# def my_ascending?(data, opts={})
#   return false if data.nil?
#   if block_given?
#     data.each_cons(2).all? { |e1, e2| yield(e1) < yield(e2) }
#   else
#     data.each_cons(2).all? { |e1, e2| e1 < e2  }
#   end
# end
# # ==> nil

# my_ascending? []
# # ==> true
# ascending? (1..1000000).to_a
# # ==> true
# my_ascending? [1,2,3,2]
# # ==> false



# Benchmark.bmbm do |x|
#   x.report('orig') { ascending? (1..1000000).to_a }
#   x.report('new') { my_ascending? (1..1000000).to_a }
# end
# # =Rehearsal ----------------------------------------
# # =orig   0.210000   0.000000   0.210000 (  0.212881)
# # =new    0.390000   0.000000   0.390000 (  0.395385)
# # =------------------------------- total: 0.600000sec
# # =           user     system      total        real
# # =orig   0.210000   0.000000   0.210000 (  0.211185)
# # =new    0.400000   0.010000   0.410000 (  0.397182)
# # ==> [#<Benchmark::Tms:0x007fd16900f5e0 @label="orig", @real=0.211185, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.20999999999999996, @total=0.20999999999999996>, #<Benchmark::Tms:0x007fd16b049c70 @label="new", @real=0.397182, @cstime=0.0, @cutime=0.0, @stime=0.009999999999999998, @utime=0.3999999999999999, @total=0.4099999999999999>]


require 'benchmark'
# ==> true

def bisect_left(a, x, opts={})
  return nil if a.nil?
  return 0 if a.empty?

  lo = (opts[:lo] || opts[:low]).to_i
  hi = opts[:hi] || opts[:high] || a.length

  while lo < hi
    mid = (lo + hi) / 2
    v = (block_given? ? yield(a[mid]) : a[mid])
    if v < x
      lo = mid + 1
    else
      hi = mid
    end
  end
  return lo
end
# ==> nil

bisect_left (1..10000000).to_a, 56789
# ==> 56788
bisect_left (1..10000000).to_a.reverse, 1
# ==> 0

def my_bisect_left(a, x, opts={})
  return nil if a.nil?
  return 0 if a.empty?

  lo = (opts[:lo] || opts[:low]).to_i
  hi = opts[:hi] || opts[:high] || a.length

  idx = if block_given?
          a[lo..hi].bsearch { |e| yield(x) <= yield(e) }
        else
          a[lo..hi].bsearch { |e| x <= e }
        end
  # if non is found, bsearch return nil
  if idx
    idx - 1
  else
    0 # insert at the beginning since all elements are bigger than us
  end

end
# ==> nil

my_bisect_left (1..10000000).to_a, 56789
# ==> 56788

Benchmark.bmbm do |x|
  x.report('orig') { bisect_left (1..10000000).to_a, 56789 }
  x.report('new') { my_bisect_left (1..10000000).to_a, 56789 }
end
# =Rehearsal ----------------------------------------
# =orig   0.460000   0.030000   0.490000 (  0.488958)
# =new    0.460000   0.030000   0.490000 (  0.493254)
# =------------------------------- total: 0.980000sec
# =           user     system      total        real
# =orig   0.460000   0.020000   0.480000 (  0.489116)
# =new    0.460000   0.020000   0.480000 (  0.494356)
# ==> [#<Benchmark::Tms:0x007f83ea80f398 @label="orig", @real=0.489116, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=0.45999999999999996, @total=0.48>, #<Benchmark::Tms:0x007f83ea80fe60 @label="new", @real=0.494356, @cstime=0.0, @cutime=0.0, @stime=0.019999999999999962, @utime=0.45999999999999996, @total=0.4799999999999999>]


def my_bisect_right(a, x, opts={})
  return nil if a.nil?
  return 0 if a.empty?

  lo = (opts[:lo] || opts[:low]).to_i
  hi = opts[:hi] || opts[:high] || a.length

  idx = if block_given?
          a[lo..hi].bsearch { |e| yield(x) <= yield(e) }
        else
          a[lo..hi].bsearch { |e| x <= e }
        end
  # if non is found, bsearch return nil
  if idx
    idx + 1
  else
    -1 # insert at the beginning since all elements are bigger than us
  end

end
# ==> nil

my_bisect_right (1..10000000).to_a, 56789
# ==> 56790