Skip to content

Instantly share code, notes, and snippets.

@kanetai
Created April 24, 2016 13:17
Show Gist options
  • Save kanetai/35fe8e2722a9318aaffa61acb6d4d53a to your computer and use it in GitHub Desktop.
Save kanetai/35fe8e2722a9318aaffa61acb6d4d53a to your computer and use it in GitHub Desktop.
cpp-like lower_bound, upper_bound in Ruby
def lowerBound(a, key)
lb = -1; ub = a.length
while ub - lb > 1
mid = (lb + ub) / 2
if a[mid] >= key
ub = mid
else
lb = mid
end
end
ub
end
def upperBound(a, key)
lb = -1; ub = a.length
while ub - lb > 1
mid = (lb + ub) / 2
if a[mid] <= key
lb = mid
else
ub = mid
end
end
ub
end
def lowerBound(a, key)
idx = (0...a.size).bsearch { |i| a[i] >= key }
#idx = bsearch_index { |e| e >= key } #Ruby 2.3 and later
idx.nil? ? a.size : idx
end
def upperBound(a, key)
idx = (0...a.size).bsearch { |i| a[i] > key }
#idx = bsearch_index { |e| e > key } #Ruby 2.3 and later
idx.nil? ? a.size : idx
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment