Log(n) Algorithm for “Rotated” Arrays
Pictured above is an array whose elements have been presorted in lexical order and then shifted, also called rotated, by S spaces. This maintains the number of elements in the array (let’s call that number N). If there was an index, i, for every element before the…