Skip to main content
2 of 2
deleted 8 characters in body; edited tags
200_success
  • 144.2k
  • 22
  • 188
  • 473

Minimum element in a sorted rotated array

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.