Minimum element in a sorted rotated array

Question

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.

Answer 1

The same can be achieved in much simpler way using Array.slice and Math.min functions:

var a = [8,1,2,3,4,3,0]; 

function findMinimum(a, start, end){
    if (a.length < end) {
        throw new Error("Invalid end range boundary!");
    }
    return Math.min.apply(null, a.slice(start, end + 1));
}

console.log(findMinimum(a, 3, 5));  // 3
console.log(findMinimum(a, 0, 2));  // 1
console.log(findMinimum(a, 1, 6));  // 0

Answer 2

If you are restricted to not using library functions, you can also simply write:

function findMinimum(a, start, end) {
    if (end > a.length || start > end) {
        throw new Error("Invalid range");
    }
    for (var i = start + 1; i <= end; i++) {
        if (a[i - 1] > a[i]) { return a[i]; }
    }
    return a[start];
}

So indeed you code is overcomplex! :- )

var a = [3,4,5,0,1,2];
console.log(findMinimum(a, 0, 5)); // 0
console.log(findMinimum(a, 0, 3)); // 0
console.log(findMinimum(a, 3, 5)); // 0

Answer 3

You do way too many comparisons.

function findminimum(arr, start, end){
    while(end > start){
        var mid = (start+end) >> 1;         
        if(arr[mid] > arr[end]){
            start = mid+1;
        }else{
            end = mid;
        }
    }
    return arr[start];
}

This code has a static complexity of \$\mathcal{O}(\log n)\$ compared to something between \$\mathcal{O}(1)\$ and \$\mathcal{O}(n)\$ in your code.

//this part may return with a single comparison and has therefore a complexity of O(1)
if(start>end || start == end || a[start]<a[end])
    return a[start];

//this part eliminates only a single element, 
//and has therefore a complexity of O(n)
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));
}