Searching Algorithms

                   -Intro to Searching
                   -Intro to Linear Search 
                   -Intro to Binary Search

Intro to Searching

Searching is a commonly used functionality for applications. Search engines such as google optimize their results based on a complex algorithm. Youtube has a search algorithm for finding and recommending videos. Searching is a fundamental procedure for applications to be useful. There are many different methods for implementing a search algorithm. Certain situations may make more sense to use a specific search over another.

Intro to Linear Search

JavaScript includes many array methods for search algorithms. Some are indexOf, includes, find, findIndex.

Linear search functions by moving one interval at a time. As well as eliminate one element at a time.

Linear Search Examples

function linearSearch(arr, val){
    for(var i = 0; i < arr.length; i++){
        if(arr[i] === val) return i;
    }
    return -1;
}

linearSearch([34,51,1,2,3,45,56,687], 100)

Intro to Binary Search

Binary search is more efficient than linear search because instead of eliminating one element at a time, its eliminates half of the remaining elements at a time.

Binary Search Example

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)