A sorted array [0,1,2,3,4,5] when rotated n times (3 times in this case) becomes [3,4,5,0,1,2], meaning elements in the front move to the end. The code below finds the minimum element in this array, which is the pivot point of rotation.
function findminimum(a, start, end){
if(start>end || start == end || a[start]<a[end])
return a[start];
var mid = start + Math.floor((end-start)/2);
//check if mid is the minimum element - also if mid is greater than start
if(mid>start && a[mid]<a[mid-1])
return a[mid];
//check if mid+1 is the minimum element - also if mid is less than end
if(mid<end && a[mid]>a[mid+1])
return a[mid+1];
//handles duplicate elements case
if(a[start]==a[mid] && a[mid]==a[end]){
//search both sides and get the minimum
return Math.min(findminimum(a, start, mid-1), findminimum(a, mid+1, end));
}
//left half is sorted or every element is same, search right half
if(a[start]<=a[mid])
return findminimum(a, mid+1, end);
return findminimum(a, start, mid-1); //search left half
}
var a = [3,4,5,0,1,2];
//original array [0,5,5,5,5] rotated 2 times
//var a = [5,5,5,0,5];
console.log(findminimum(a, 0, a.length-1));
Code also handles duplicates. Any comments or suggestions on improving this code will be helpful.