Skip to content

Instantly share code, notes, and snippets.

@pzaich
Created August 17, 2016 04:52
Show Gist options
  • Save pzaich/a9acbbc1b7efc781d2c32e164e2131d5 to your computer and use it in GitHub Desktop.
Save pzaich/a9acbbc1b7efc781d2c32e164e2131d5 to your computer and use it in GitHub Desktop.
Find Rotation Point of mostly sorted array of words
// simple O(n), linear method
function linearFindRotationPoint(array) {
var rotationPointIndex;
for (var i = 1; i <= array.length; i++) {
if (array[i-1] > array[i]) {
rotationPointIndex = i;
break;
}
}
return rotationPointIndex;
}
console.log(linearFindRotationPoint(words))
// O(log(n)) modified binary search
function logNFindRotationPoint(array) {
var center = Math.floor(array.length / 2);
var centerWord = array[center];
var left = array[center - 1];
var right = array[center + 1];
if (centerWord < left) {
return center;
} else if (centerWord > right) {
return logNFindRotationPoint(array.slice(0, center - 1));
} else {
return logNFindRotationPoint(array.slice(center + 1, array.length - 1));
}
}
console.log(logNFindRotationPoint(words))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment