Binary Search

Today I'll be going over binary search, a search algorithm that finds the position of a target value in a sorted array.

It works by repeatedly halving the portion from the list that could contain the item until you land on the intended target. We start from the middle of the list and depending on the condition, we manipulate the range to eliminate a half of the list.

Let's take a look at a classic binary search problem: Find an element position in a sorted array. We have the target element and we want to return the index/position of it.

const binarySearch = (arr,target) => {

    let left = 0
    let right = arr.length - 1
    let boundary_index = -1

    while(left <= right){
        let mid = left + Math.trunc((right - left) / 2);
        if(arr[mid] === target){
            return mid
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1
}

The way we implement binary search is by first creating the range in which the element could reasonably be. In this while loop, we are constantly searching the middle element of the array and checking for three things:

1: Is the current element the target? If it is, we return the index.

2: Is the current element smaller than the target? If it is, we know that everything to the left of this element cannot be the target. Therefore, we make the left boundary of the range mid + 1.

1. Is the current element larger than the target? If it is, we know that everything to the right of this element cannot be the target. Therefore, we make the right boundary of the range mid - 1.

We can assume these things because the array is sorted in ascending order. The values become larger as we go to the right of the list. If we never find the index, we return -1.