Searching Algorithms

Intro to Linear Search

-> Checking every single thing at a set interval on item at a time

-> many different search methods on arrays in JavaScript

- indexOf, includes, find, findIndex

 

Linear Search Pseudocode

• Loop through the array and check if the current array element is equal to the value
• If it is, return the index at which the element is found
• If the value is never found, return -1

Linear Search Big O

as far as time complexity is concerned,

O(1) best - find thing right away

O(n) average - as the length grows so does the average amount of time it takes.

O(n) worst - very last element

 

---

Intro to Binary Search

• much faster form of search
• you can eliminate half of the remaining elements at a time
• only works on sorted arrays. there has to be an order to it.

 

Binary Search on sorted arrays

- create a left pointer at the start of the array,

and a rignt pointer at the end of the array

- while the left pointer comes before the right pointer

  - create a pointer in the middle

  - if you find the value you want, return the index

  - if the value is too small, move the left pointer up

  - if the value is too large, move the right pointer down 

- if you never find the value, return -1

 

function binarySearch(arr, searchVal){
    let temp=0;
    let end= arr.length-1;
    
    while(temp !== (end+temp)/2) {
        if(arr[temp] < searchVal){
            temp = Math.floor((end+temp)/2);
        } else if(arr[temp] > searchVal) {
            end = temp;
            temp = Math.floor(temp/2);
        }
        
        if(arr[temp] === searchVal) return temp;
    }
    return -1;
    
}

binarySearch([1,2,3,4,5],5);

// Original Solution
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

// Refactored Version
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)

 

Binary Search Big O

O(log n) - worst and average case

every tiem double it ,simply adding one extra step

O(1) - best case

---

Naive String Searching Algorithm

- searching for substrings in a larger string 

 

function naiveSearch(long, short){
    var count = 0;
    for(var i = 0; i < long.length; i++){
        for(var j = 0; j < short.length; j++){
           if(short[j] !== long[i+j]) break;
           if(j === short.length - 1) count++;
        }
    }
    return count;
}

naiveSearch("lorie loled", "lol")