Searching

I am working my way through learning data structures and algorithms. One algorithm that works very well in improving Big O time complexity is a Binary Search, which improves on a basic linear search. In order to use Binary Search however the items that you’re searching through must be sorted.

Photo by Markus Winkler on Unsplash

I will begin by showing a linear search and how it works and how a binary search improves on this. How linear search works is it goes through each item and checks if it is equal to the item you are searching for. I will give the code for a linear search (in JavaScript) and for this example, the code will receive an array and value of the item we are searching for:

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

If we find the value we are looking for we return the index of that value in the array otherwise we return -1 meaning we couldn’t find the value in the array. This could be effective for a best-case scenario we find our value in the first item of the array and we return 0 (for index 0), but we can rely on finding what we are looking for right away or finding the value at all. So, for our worst-case and also average Linear search gives us a Big O of O(n) as it goes through each value of the array.

Binary Search

As I mentioned before the items must be sorted in order to use a binary search. But given that the items are sorted we can much more effectively use a search function. The way the binary search works is by using a pointer for a start point, endpoint, and middle point (can also be left point, right point, and middle). The search starts by looking at the middle value if the middle value is what we are looking for then we are done. Otherwise, we see if the value we’re looking for is greater than or less than the middle value. If the value we are looking for is greater than the middle value, we disregard the middle value and everything below it. Then the new start point becomes the value after the middle value and the new middle value is the middle between the new start point and the endpoint. Similarly, if the value we are looking for is less than the middle value, we would do the opposite. Which would be to disregard the middle value and everything above it. Then the new endpoint becomes the value before the middle value and the new middle value is the middle between the start point and the new endpoint. This process is repeated until either the item is found or we determine what we are searching for doesn’t exist in the array.

function binarySearch(arr, val){
    let left = 0
    let right = arr.length - 1
    let middle = Math.floor((right + left)/2)
    
    while(arr[middle] !== val && left <= right){
        if(val < arr[middle]){
            right = middle - 1
        } else {
            left = middle + 1
        }
        middle = Math.floor((right + left)/2)
    }
    if(arr[middle] === val){
        return middle
    }
    return -1
}

We can see that this function is much more effective than a regular linear search because as we run through it we are dividing the array we are searching in half, therefore halving the number of values we have to search through on each loop. This function gives us a much better Big O time efficiency of O(log n).

The Udemy courses JavaScript Algorithms and Data Structures Masterclass & Master the Coding Interview: Data Structures + Algorithms helped me learn and work my way through searching algorithms.