Leetcode - Binary Search (with JavaScript)

Today I am going to show how to solve the Binary Search algorithm problem.

Here is the problem:

Binary search algorithm is one of the most famous searching algorithms. Even though it is not very difficult to understand, it is very important that we understand it thoroughly and know how to properly implement it.

Binary search algorithm helps us to find the position of a target value within a sorted array. It gives us O(log n) time complexity.

Binary search compares the target value to the middle element of the array. If they are not equal, based on that comparison either the first half or the second half of the array is selected while the other one is eliminated. The search then continues on the remaining half. The middle element is again compared to the target value. This process repeats itself until the target value is found.

First, I am going to declare two pointers to solve this problem:

• Left pointer, which is going to point to the first number in the array and;
• Right pointer, which is going to point to the last number in the array.

Then, I calculate the middle number by taking the sum of the left pointer and the right pointer and dividing that by two. Since we're dealing with indices and we know that an index cannot be a decimal number, we have to round this number down.

Now that we have the middle number, we are going to compare it to our target number.

• If they are equal, we will return the index of the middle number.
• If the middle number is less than the target number, we will eliminate the second half of the array on the right side of the middle number. We will then move our left pointer and repeat this until the target value is found.
• If the middle number is more than the target number, we will eliminate the first half of the array on the left side of the middle number. We will then move our right pointer and repeat this until the target value is found.

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = Math.floor((left + right) / 2);
        const potentialMatch = nums[middle];
        if(target === potentialMatch) {
            return middle;
        } else if (target < potentialMatch){
            right = middle - 1;
        } else {
            left = middle + 1
        }
    }
    return -1
};