[Algorithm] How many times is a sorted array rotated?

Given a sorted array, for example:

// [2,5,6,8,11,12,15,18]

Then we rotated it 1 time, it becomes:

// [18, 2,5,6,8,11,12,15]

2 times:

// [15,182,5,6,8,11,12]

 

So now given you an array which is rotated N times based on an sorted array, try to find the what is the N?

 

Key point is, the smallest value in the array (if rotated happened), it must smaller than its previous and next element.  Using binary search to reduce numbers of elements we are searching each time.

 

function countRotated (ary) {
  let N = ary.length,
      low = 0,
      high = N - 1;
  
  while (low <= high) {
    // case 1: ary is sorted already, no rotated
    if (ary[low] < ary[high]) {return low;}
    let mid = Math.floor((low + high) / 2);
    // if mid is the last element, then we need to go to first element in the array, %N does that
    let next = (mid + 1) % N;
    // if mid is the first element, prevent -1 index
    let prev = (mid - 1 + N) % N;
    // case 2: if mid is smaller than next and prev element, then it must be the smallest item in the array
    if (ary[mid] < ary[next] && ary[mid] < ary[prev]) {
      return mid;
    }
    // case 3: if mid is smaller than high, then it means pivot element is not on the right side
    else if (ary[mid] < ary[high]) {
      high = mid - 1;
    }
    // if mid is larger than low, then it means pivot element is not on the left side
    else if (ary[mid] > ary[low]) {
      low = mid + 1;
    }
  }
  
  return -1;
}

const data = [8,9,10,11,12,15,18,2,5]; // 7
const data2 = [11,12,15,18,2,5,6,8]; // 4
const data3 = [11,12,15,18,2,5,6,8,9,10]; // 4
const data4 = [1,2,3,4,5,7,8]; // 0
const res = countRotated(data);
console.log(res);
const res2 = countRotated(data2);
console.log(res2);
const res3 = countRotated(data3);
console.log(res3);
const res4 = countRotated(data4);
console.log(res4);