How To Do Binary Search In Javascript | Binary Search - letsbug

   Binary Search is one of the most important searching algorithm and today's article is on it.  Binary search is a quicker method to search than linear search. But it cannot be applied to unsorted data structures. The binary search is based on the approach divide-and-conquer. 

Binary Search In Javascript

    The binary search starts by testing the data in the middle element of the array. This determines target is whether in the first half or second half. If target is in first half, we do not need to check the second half and if it is in second half no need to check in first half.

    And similarly we repeat this process until we find target in the list or not found from the list. Here we need 3 variable to identify first, last and middle element. This algorithm can be Iterative or recursive.

Below is the code of binary search in javascript.

/**

 *

 * @param {Array<Number>} arr is array

 * @param {Number} x

 * is the element to find in array arr

 * @returns {Number} the position of element in arr

 */

function binarySearch(arr, x) {

    let low = 0

    let high = arr.length - 1

    let mid

    while (low <= high) {

        mid = Math.floor((low + high) / 2);

        if (arr[mid] < x) {

            low = mid + 1

        } else if (arr[mid] > x) {

            high = mid - 1

        } else {

            return mid

        }

    }

    return -1

}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

let result = binarySearch(arr, 4)

console.log(result)

    In the above code in the binarySearch function we start by first initializing 3 three variables which are low, high and mid. And as this is a iterative example so we then use while loop to iterate over the loop.

    While low <= high we set the mid variable to the middle of the array. And then using if checks we determine weather the element is in the first half or not and accordingly change the value of low and high variable. 

    This logic is not limited to one language you can use this logic and impliment binary search in any programming langauage you preffer.

Thankyou