DEV Community

Manthan Bhatt
Manthan Bhatt

Posted on

2 2

Implement Binary Search Using JavaScript

Binary search technique is used to search for any element in a sorted array using divide and conquer approach.

/**
 * Binary Search
 * Note - It works only for the sorted array. start and end are left and right of the array.
 *
 * Recursive Approach
 * - If starting index is greater than the ending index return false
 * - Compute the middle index.
 * - Compare the middle element with the number x. If equal return true.
 * - If greater, call the same function with ending index = middle-1 and repeat step 1.
 * - If smaller, call the same function with starting index = middle+1 and repeat step 1.
 * 
 * Time Complexity: O(logN)
 * Auxiliary Space: O(1)
 */

const arr = [1, 3, 5, 7, 8, 9];

const binarySearchRecursive = (arr, val, start, end) => {
    if (start > end) return false;

    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === val) return mid;

    const left = arr[mid] > val ? start : mid + 1;
    const right = arr[mid] > val ? mid - 1 : end;

    return binarySearchRecursive(arr, val, left, right);
}

console.log(binarySearchRecursive(arr, 5, 0, arr.length - 1)); // -> 2
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay