DEV Community

Write better code: Day 3 - Rotation Point

Arjun Rajkumar on December 07, 2018

This post originally appeared on Arjun Rajkumar 's blog. Arjun is a web developer based in Bangalore, India. -- Day 3: Question 2 I op...
Read full post
Collapse
 
arjunrajkumar profile image
Arjun Rajkumar •

This was very similar to binary search as it was mostly sorted. Just had to keep splitting until the mid word was lesser than starting word.

def rotation_point(words)
  starting_index = 0
  ending_index = words.length - 1

  while starting_index < ending_index

    puts "\n#{words[starting_index]}"
    puts "#{words[ending_index]}"

    mid = (starting_index + ending_index) /2
    puts "#{mid}"
    puts "#{words[mid]}"
    if words[mid] < words[0]
      ending_index = mid 
    else
      starting_index = mid
    end

    return ending_index if starting_index + 1 == ending_index
  end
end

Binary search so its O[logn] time and space if O[1]

Collapse
 
phlash profile image
Phil Ashby •

Nice. There is a similar real world problem when writing journalling file systems: they need to find the rotation point of the journal, even after a system failure that didn't permit saving that information anywhere well known. The solution is similar too, a binary search through disk blocks looking for the point where the journal index goes down instead of up :)