Intro to Algorithms

algos.js

/*
 original [7,4,12,39,6.5,88,78,-3,14.7,3.14,359]
 pass 1   [-3,7,12,39,6.5,88,78,4,14.7,3.14,359]
 pass 2   [-3,3.14,12,39,7,88,78,6.5,14.7,4,359]
 pass 3   [-3,3.14,4,39,12,88,78,7,14.7,6.5,359] 

We want to sort this array from smallest to largest

1. Look at each number in the array
2. Look at each number that comes after that number
3. Compare the two numbers. If the second number is smaller than
the first number, swap them.
4. Repeat step 1 with next number in the array
5. Stop when we reach the 2nd to last number in the array
*/

//function sort takes an unsorted array of numbers
function sort(array) {

  //look at each number in the array (step 1, 4, 5)
  for (let i=0; i < array.length-1; i++) {
    //look at each number that comes after the number at position 1 (step 2)
    for (let j=i+1; j < array.length; j++) {
      //compare the numbers at position i and j in array (step 3)
      if (array[i] < array[j]) {
        //Swap values of array[i] and array[j]
        let holdMyBeerArrayI = array[i];
        //number at position i is bigger, so swap them
        //array[i] = 7, array[j] = 4
        array[i] = array[j];
        //array[i] = 4, array[j] = 4
        array[j] = holdMyBeerArrayI;
        //array[j] = 7
      }
    }
  }
  //return same array after it is sorted
  return array;
}

let unsortedNumbers = [7,4,12,39,6.5,88,78,-3,14.7,3.14,359];

let sortedNumbers = sort(unsortedNumbers);

//console.log("sorted:  ",sortedNumbers); 


/*
original: [ -3, 3.14, 4, 6.5, 7, 12, 14.7, 39, 78, 88, 359 ]
pass 1:   [ -3, 3.14, 4, 6.5, 7, 12, 14.7, 39, 78, 88, 359 ]
mid = 5 

We are looking to see if a number exists in an array
1. Look at the element in the middle of the array. Is it greater than, equal to, or less than the element we are looking for?
2. If the current element is equal to the value we are looking for, then great! We are done. The algorithm can return true and the algorithm ends.
3. If the current element is less than the element we are looking for, discard it and the elements before it in the array.
4. If the current element is greater than the element, discard it and the elements after it in the array.
5. If the array is empty, we did not find the element. Return false. Otherwise, repeat step 1-4 on the remaining elements.
*/

//function to look for numberToFind in array, using a binary search
function binarySearch(numberToFind, array) {

  let holdMyBeerArray = array.slice(0);
  console.log(holdMyBeerArray);
  while (holdMyBeerArray.length > 0) {
    let length = holdMyBeerArray.length;
    //We want to make sure this number is always a whole number
    let mid = Math.floor(length / 2);

    if (holdMyBeerArray[mid] === numberToFind) {
      return true;
    }

    if (holdMyBeerArray[mid] < numberToFind) {
      holdMyBeerArray.splice(0, mid+1);
    }

    if (holdMyBeerArray[mid] > numberToFind) {
      holdMyBeerArray.splice(mid);
    }

    console.log(mid, holdMyBeerArray);
  }

  return false;
}

let array2 = [ -3, 3.14, 4, 6.5, 7, 12, 14.7, 39, 78, 88, 359 ];

console.log(binarySearch(360, array2));
console.log(binarySearch(-3, array2));
console.log(binarySearch(78, array2));