Skip to content

Instantly share code, notes, and snippets.

@moserrya

moserrya/shifted_sorted.rb

Created April 22, 2013 22:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save moserrya/5439201 to your computer and use it in GitHub Desktop.
Save moserrya/5439201 to your computer and use it in GitHub Desktop.
Download ZIP
Find the smallest number in a shifted sorted array that runs in log(n) time
Raw
shifted_sorted.rb
def find_index(ary, index = 0)
midpt = ary.length / 2
if midpt <= 1
return ary.first < ary.last ? index : index + 1
end
left, right = ary[0...midpt], ary[midpt..-1]
if left.last > left.first && ary.last < ary.first
index += midpt
find_index(right, index)
else
find_index(left, index)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment