Linear Search

Linear search works by checking each element in order.

Binary Search

Binary search works by repeatedly checking if what you are searching for is greater than or less than the middle number, then refining what area it looks at. Binary search requires a sorted list which currently looks like:

Bubble Sort

Bubble sort swaps pairs of number that are out of order, bubbling bigger numbers to the top, until the list is sorted.

Selection Sort

Selection sort searches for the next smallest element in a list, then moves it to the back of the sorted part of the list.

Source Code

• searchLinear Search

  
  
  function linearSearch(target, array) {
    for (let i = 0; i < array.length; i++) {
      if (array[i] === target) {
        return i;
      }
    }
    return null; // Not found
  }
                  

• account_treeBinary Search

  
  // array must be sorted
  function binarySearch(target, array) {
    let low = 0;
    let high = array.length - 1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2); // mid point between high and low
  
      /* 3 options:
       * 1. the target is in the lower half -> reduced the top bound to only include unsearched values
       * 2. the target is in the upper half -> increase the bottom bound to only include unsearched values
       * 3. we found the target             -> return the location
       */
      if (target < array[mid]) {
        high = mid - 1;
      } else if (array[mid] < target) {
        low = mid + 1;
      } else {
        return mid;
      }
    }
    return null; // Not found
  }
                  

• bubble_chartBubble Sort

  
  function bubbleSort(array, ascending = true) {
    // creates a different function if ascending is true or false
    let compare = ascending ? (a, b) => a < b : (a, b) => a > b; // true if [a, b] *is in* ascending/descending order
  
    // i: end -> beginning ; stores the index of where the sorted part begins
    for (let i = array.length - 1; i > 0; i--) {
      // j: beginning -> i ; bubble through the unsorted part
      for (let j = 0; j < i; j++) {
        // the 'j'th and 'j+1'th element are out of order
        if (compare(array[j + 1], array[j])) {
          // swap j and j+1 in array
          let temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
    }
    return array;
  }
  
                  

• sortSelection Sort

  
  function selectionSort(array, ascending = true) {
    // creates a different function if ascending is true or false
    let compare = ascending ? (a, b) => a < b : (a, b) => a > b; // true if [a, b] *is in* ascending/descending order
  
    // sort all but the last element (which will already be sorted)
    for (let i = 0; i < array.length - 1; i++) {
      let toMove = i; // could be index of max or min of remaining unsorted list
                      // based on if sorting ascending or descending
  
      // select the next biggest/smallest element to move to array[i]
      for (let j = i; j < array.length; j++) {
        // array[j] is greater or less than the current value to be moved
        if (compare(array[j], array[toMove])) {
          toMove = j;
        }
      }
      // swap i and toMove in array
      let temp = array[i];
      array[i] = array[toMove];
      array[toMove] = temp;
    }
    return array;
  }