logn array shift

by rgthree

JavaScript

function _t(arr, shouldBe){
  var start, end, look, answer, safety;
    answer = null;
    start = 0;
    end = arr.length - 1;
    look = Math.floor(end/2);
    safety = 0;
    // Array is already in order, we've shifted 0
    if(arr[start] < arr[end]){
        answer = 0;
        console.log('skip');
    }
    while(answer === null && safety < 100){
        //console.log(start+' '+look+' '+end)
        
        // First half is our half
        if(arr[start] > arr[look]){
            end = look;
            look = Math.floor((end - start) / 2)+start;
            
        // Second half is our half
        }else if(arr[end] < arr[look+1]){
            start = look+1;
            look = Math.floor((end - start) / 2)+start;
        
        // We've found our answer, first and second half pass,
        // so our answer is look+1
        }else{
            answer = look+1;
        }
        
        // If we have no answer yet and we only have one item,
        // then we've found our answer
        if(answer === null && end-start === 1){
            answer = end;
        }
       
        safety++;
    };
    console[answer === shouldBe ? 'log':'error'](answer+' ('+shouldBe+')');
}

// Test cases, each array is shifted and iterated over and the current shift should match the "shouldBe" variable above.
console.clear();
var a,i,l;
[
    [0,1,2,3,4],
    [0,1,2,3,4,5],
    [0,1,2,3,4,5,6,7,8,9],
    [11,12,34,56,788,945,1001,12003],
    [20,21,22,24,26,33,35,37,38,41,42,43,45,47,48,51,53,54,57,58,59,60,61,62,63,64,65,66,68,70,71,72,74]
].forEach(function(a){
for(i = 0, l = a.length; i < l; i++){
    console.log('---',JSON.stringify(a));
    _t(a, i);
    a.unshift(a.splice(a.length-1,1)[0]);
}
});