Rotation point

Write a function for finding the "rotation point". This array is huge so we want to be efficient here.

Example

i/p: [35,42,5,15,27,29]
o/p: 2

Solution

• Use the binary search technique to find the rotation point
• When the left and right pointers are next to each other we have found the rotation point

Code

def find_rotation_point(array)
  left = 0
  right = array.size

  first = array[0]

  while left < right
    mid = (left + right) / 2

    array[mid] > first ? left = mid : right = mid

    return right if left + 1 == right

  end
end

Complexity

• O(log n) since we are using the binary search technique to eliminate half of the array in each iteration
• We're using constant space O(1) for maintaining the left, right and mid indices