Algorithms

Question 1

Binary Search

Overview

Answer 1

An Algorithm that looks up a target in a sorted list. it returns the index of the target within the array. It cuts the searchable area in half on each iteration

Question 2

Binary Search

Pros and Cons

Answer 2

In it’s worst case, it outperforms linear search by cutting the searchable area in half on each iteration (binary logarithm [Ologn] where n is number of inputs)
So, as the input doubles, we only perform one more operation to find the target

Question 3

Binary Search

Big O

Answer 3

Big Ologn

n is the number of inputs. log is base 2 (Binary logarithm)

Question 4

Binary Search

What problems can this solve

Answer 4

quickly finding targets in sorted arrays/lists

Leetcode problems

Question 5

Binary Search

Think it, Write it, Code it

1. What does the method do
2. What’s the BigO
3. What are the params and return values
4. What are the code steps

Answer 5

/**
 * Binary search
 * Ologn - binary logarithmic
 * @param {number} target lookup value
 * @param {Array} arr sorted array
 * @returns {number} the index of the target in the array. -1 if not found in array.
 */
function binarySearch(target, arr){

    let high = arr.length;
    let low = 0;
    let mid = Math.floor((high + low)/2)
    if(arr[0] === target) return 0;

    while(low !== mid && high !== mid){
        if(target > arr[mid]){
            low = mid;
        }else if(target < arr[mid]){
            high = mid;
        }else{
            return mid
        }
        mid = Math.floor((high + low)/2)
    }
    return -1
}