2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ the expression console.log(findminimum(a, 4, a.length-1)); returns 1. Is that correct result for your function(according to its name 'findminimum') ? \$\endgroup\$ – RomanPerekhrest Mar 23 '16 at 20:03
  • \$\begingroup\$ 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 ? \$\endgroup\$ – Software Engineer Mar 23 '16 at 21:19
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What is the time and space complexity of this approach ? \$\endgroup\$ – janos Mar 23 '16 at 23:13
  • \$\begingroup\$ @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 ... \$\endgroup\$ – RomanPerekhrest Mar 24 '16 at 22:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – janos Mar 24 '16 at 22:39
  • \$\begingroup\$ 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 \$\endgroup\$ – RomanPerekhrest Mar 24 '16 at 22:44
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yeah, but looks like the time complexity would be O(n) in this case, whereas binary search would yield O(log n); \$\endgroup\$ – Software Engineer Mar 24 '16 at 0:03
0
\$\begingroup\$

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));
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.