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.

• the expression console.log(findminimum(a, 4, a.length-1)); returns 1. Is that correct result for your function(according to its name 'findminimum') ? – RomanPerekhrest Mar 23 '16 at 20:03
• Yes, because the range you are checking for a minimum element seems to be starting from 4 until end of the array, which means for elements [1,2]. What is the input array that you are testing it on ? – Software Engineer Mar 23 '16 at 21:19

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

• What is the time and space complexity of this approach ? – janos Mar 23 '16 at 23:13
• @janos, what do you mean? If I understand correctly, the goal was to find the minimum within a range of array values. We have the original array, lower and upper bounds for the range to find the minimum, that's all ... – RomanPerekhrest Mar 24 '16 at 22:07
• OP's algorithm looks like a binary search, making it $O(\log(N))$ time complexity, and without additional storage, $O(1)$ space complexity. Your suggestion looks like a linear search, making it $O(N)$ time complexity, and I'm not sure about the space complexity because I don't know if Array.slice will create arrays. If my assumptions are correct, then your suggestion is slower. But I didn't have time to look too close, so asked you directly instead. – janos Mar 24 '16 at 22:39
• yes, I think it acts like a linear search for "static"(fixed) array size. Secondly, yes,Array.slice will create a new array from slice fragment – RomanPerekhrest Mar 24 '16 at 22:44

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

• Yeah, but looks like the time complexity would be O(n) in this case, whereas binary search would yield O(log n); – Software Engineer Mar 24 '16 at 0:03

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));
}