DEV Community

stuxnat
stuxnat

Posted on

JavaScript: Binary Search

Today I will be writing about how to solve the Binary Search algorithm problem on Leetcode.

The problem:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

var search = function(nums, target) { 
};
Enter fullscreen mode Exit fullscreen mode

Step 1. Create 2 pointers, left and right to point to the beginning and end of the array.

var search = function(nums, target) {
    let left = 0; 
    let right = nums.length - 1 
};
Enter fullscreen mode Exit fullscreen mode

Considering the given example array [-1,0,3,5,9,12], left would point to -1 and right would point to 12.

Step 2. Create while loop.
We will set left = right because they will eventually meet. We also want to find a middle element.

var search = function(nums, target) {
    //step 1. create 2 pointers, left and right to point to first and last elements. 
    let left = 0; 
    let right = nums.length - 1 

    while (left <= right){
        let middle = left + Math.floor((right - left) / 2)
    }
};
Enter fullscreen mode Exit fullscreen mode

Step 3. Write if-statement to calculate middle element.
If the middle element === target, return middle.

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

    while (left <= right){
        let middle = left + Math.floor((right - left) / 2)

            if(nums[middle] === target){
                return middle 
            } else if (middle < target) {
                left = middle + 1  
            } else { 
                right = middle - 1
            }
    }
};
Enter fullscreen mode Exit fullscreen mode

Step 4. Return -1 if element does not match target.



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

    while (left <= right){
        let middle = left + Math.floor((right - left) / 2)

            if(nums[middle] === target){
                return middle 
            } else if (middle < target) {
                left = middle + 1  
            } else { 
                right = middle - 1
            }
    }
return -1
};


Enter fullscreen mode Exit fullscreen mode

Discussion (0)