Divide and Conquer Algo for Searching a Sorted, Rotated Array

RotatedArrayDCSeach.js

// Going to create a way to search a rotated array that uses a divide and conquer approach rather than the standard binary tree method

var maxNumber = 50000// Or use something like  Math.pow(2,31) to create a large binary integer; // A 32 bit integer, since bitwise only works on 32 bit ints

function splitList(arr, sections) {
  // arr = the list we're searching
  // num = the number we're searching for
  // sections = the number of sections to break the larger list into
  
  var a = []; // Create a new array to hold the multiple arrays
  var startIndex = 0; // The index to slice from
  for(var i = 0; i < sections; i++) {
    // Jump through the array creating new arrays
    a[a.length] = arr.slice(startIndex, startIndex + (arr.length / sections) - 1);
    startIndex += arr.length / sections; // Update start index for the next loop
  }
  
  return a; // Return the new array of arrays
}


function findInArray(arr,num) {
  // If we're here, it means we've continuously divided down the array until we have less items to check than the number of sections we plan to break the array into and it is now time to just search for the item
  var numInArray = false; // We expect to find that the number is not in the array
  for(var i = 0; i < arr.length; i++) {
    if(arr[i] === num)
      numInArray = true; // Number is in the array, so set to true
  }
  
  return numInArray;
}


function findInSections(arr, num, sections) {
  
  if(sections >= arr.length) {
    return findInArray(arr,num);
  }
  
  var a = splitList(arr, sections);
  
  for(var i = 0; i < sections; i++) {
    // We're going to check each section of the array starting at the beginning
    if(a[i][0] === num) {
      // First let's do just some simple pruning, if a[i][0] happens to be equal to the number, then
      return true;
    }
    
    if(a[i][0] > num) {
      // If a[i] is greater than our number, we need to check the next section against it
      if(a[i+1][0] < a[i][0]) {
        // If we're here, we've found that the array rotates somewhere in a[i].
        if(a[i+1][0] > num) {
          // Now we know for sure we will find num in a[i] or not at all
          return findInSections(a[i],num,sections);
        }
      } else {
        // If a[i+1][0] is still greater than our number
        if(i + 1 === sections - 1) {
          // The next section is the last section, we'll find our number there or not at all
          return findInSections(a[i+1],num,sections);
        }
      }
    } else {
      // a[i][0] is less than our number
      if(i === sections - 1) {
        // This is the last section, so we will find the number here or we won't find it
        return findInSections(a[i],num,sections);
      } else {
        // a[i] isn't the last section
        if(a[i+1][0] > num) {
          return findInSections(a[i],num,sections);
        }
      }
    }
  }
  
  return false; // If we get to here, then we haven't found the number and we return false.
}

// Some testing code follows to generate and then rotate a random array of integers

function genArray(n) {
  var a = [];
  for(i=0; i< n; i++) {
    a[a.length] = Math.random() * maxNumber | 0;
  }
  a.sort(sortCompare);
  
  
  return a;
}

function rotateArray(arr) {
  var shiftIndex = (Math.random() * maxNumber | 0) % arr.length;
  for (i = 0; i < shiftIndex ; i++) {
    var shiftElement = arr.shift();
    arr[arr.length] = shiftElement;
  }
  return arr;
}

var sortCompare = function(a, b) {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
};


function doTest() {

  var end, start, num;
  var arr = genArray(maxNumber/2); // set maxNumber at the top of this file.
  var num = 6; // set the number to search for here
  var sectionsToCreate = // set the number of sections to break the list into here

  var rotArr = rotateArray(arr);

  start = new Date(); // Start the clock to time the operation
  var isNumberInArray = findInSections(rotArr,num,sectionsToCreate);
  end = new Date(); // Stop the clock on the operation.
  
  console.log("The D&C operation took " + (end.getTime() - start.getTime()) + " msec");
  console.log("Is the number " + num + " in the array? " + isNumberInArray);

}

doTest();