Binary Search in JavaScript

Binary Search is searching technique which works on Divide and Conquer approach. It used to search any element in a sorted array. As compared to linear, binary search is much faster with Time Complexity of O(logN) whereas linear search algorithm works in O(N) time complexity.

In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for right side of middle element.

Recursive Binary Search

const bs_recursive = (arr, target, start, end) => { 
    // Base Condition 
    if (start > end) return false; 
    // Find the middle index 
    let mid=Math.floor((start + end)/2); 
    // Compare mid with given key target 
    if (arr[mid]===target) return true; 
    // If element at mid is greater than target, 
    // search in the left half of mid 
    if(arr[mid] > target)  
        return bs_recursive(arr, target, start, mid-1); 
    else
        // If element at mid is smaller than target, 
        // search in the right half of mid 
        return bs_recursive(arr, target, mid+1, end); 
} 

Iterative Binary Search

const bs_iterative = (arr, x) => { 
    let start=0, end=arr.length-1; 
    // Iterate while start not meets end 
    while (start<=end){ 
        // Find the mid index 
        let mid=Math.floor((start + end)/2); 
        // If element is present at mid, return True 
        if (arr[mid]===x) return true; 
        // Else look in left or right half accordingly 
        else if (arr[mid] < x)  
             start = mid + 1; 
        else
             end = mid - 1; 
    } 
    return false; 
} 

Binary Search Function

function bsearch(A, target){
    console.log("\nsource: ", A)
    A.sort((a,b)=>a-b) // must use sorted array for binary search
    console.log("sorted: ", A)
    console.log("target: ", target, " ,bs_recursive: ", bs_recursive(A, target, 0, A.length-1))
    console.log("target: ", target, " ,bs_iterative: ", bs_iterative(A, target))
}
const arr = [7, 3, 1, 5, 8, 9]
const target1 = 5
const target2 = 6
bsearch(arr, target1)
bsearch(arr, target2)

Output:
source: [ 7, 3, 1, 5, 8, 9 ]
sorted: [ 1, 3, 5, 7, 8, 9 ]
target: 5 ,bs_recursive: true
target: 5 ,bs_iterative: true

source: [ 1, 3, 5, 7, 8, 9 ]
sorted: [ 1, 3, 5, 7, 8, 9 ]
target: 6 ,bs_recursive: false
target: 6 ,bs_iterative: false