Binary Search in JavaScript

Recursive Approach

Binary search can be implemented recursively by continuously dividing the array into two halves and searching in the appropriate half.

Code Implementation

function binarySearchRecursive(arr, target, left, right) {
    if (left > right) {
        return -1; // Element not found
    }
    let mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
        return mid; // Element found
    } else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
let index = binarySearchRecursive(arr, target, 0, arr.length - 1);
console.log(index); 

You can also try this code with Online Javascript Compiler

Run Code

Output: 

3

Explanation:

• The function checks if left is greater than right, indicating the element is not found.
   
• It calculates the middle index.
   
• If the middle element matches the target, it returns the index.
   
• If the target is smaller, it searches in the left half.
   
• If the target is larger, it searches in the right half.

Iterative Approach

An iterative approach avoids recursion by using a while loop to continuously narrow down the search range.

Code Implementation

function binarySearchIterative(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Element found
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; // Element not found
}

let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
let index = binarySearchIterative(arr, target);
console.log(index); 

You can also try this code with Online Javascript Compiler

Run Code

Output: 

3

Explanation:

• We start with two pointers, left at the start and right at the end of the array.
   
• We calculate the middle index.
   
• If the middle element matches the target, we return the index.
   
• If the target is smaller, we move the right pointer to mid - 1.
   
• If the target is larger, we move the left pointer to mid + 1.
   
• If the loop exits without finding the target, -1 is returned.

Time & Space Complexity of Binary Search in Javascript

Binary search is known for its efficiency, but to understand why, we need to look at its time & space complexity. Time complexity refers to how long an algorithm takes to run, while space complexity refers to how much memory it uses.

Time Complexity

Binary search has a time complexity of O(log n), where n is the number of elements in the sorted list. This means that with every step, the algorithm reduces the search space by half. For example, if you have 1000 elements, binary search will take at most 10 steps to find the target (since 2^10 = 1024). In contrast, a linear search would take up to 1000 steps in the worst case.

Space Complexity

The space complexity of binary search is O(1), which means it uses a constant amount of extra memory. This is because binary search doesn’t require additional data structures or recursion (if implemented iteratively). It only needs a few variables to keep track of the search interval.

Let’s look at a simple example to understand this better:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);


        if (arr[mid] === target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            left = mid + 1; // Search the right half
        } else {
            right = mid - 1; // Search the left half
        }
    }
    return -1; // Target not found
}

In this code, the `left` & `right` pointers define the search interval, & the `mid` pointer is calculated to divide the array into two halves. The loop continues until the target is found or the interval is exhausted. This implementation uses constant space, as only a few variables are needed.

The Efficiency of Binary Search in Javascript

Binary search is efficient because it eliminates half of the remaining elements with each step. This makes it significantly faster than linear search, especially for large datasets. Let’s understand why this is the case.

How Binary Search Works

1. Sorted List Requirement: Binary search requires the list to be sorted. This is because it relies on comparing the target value with the middle element to decide which half to search next.
 

2. Divide & Conquer: The algorithm repeatedly divides the search interval in half. If the target is less than the middle element, it searches the left half. If it’s greater, it searches the right half.
 

3. Termination: The search ends when the target is found or the interval becomes empty (meaning the target is not in the list).

Practical Example

Suppose you have a sorted array of numbers:

const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const target = 11;

Let’s see how binary search works step-by-step:

1. Start with the entire array: `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]`.
 

2. Compare the target (11) with the middle element (9). Since 11 > 9, search the right half: `[11, 13, 15, 17, 19]`.
 

3. Compare 11 with the middle element (15). Since 11 < 15, search the left half: `[11, 13]`.
 

4. Compare 11 with the middle element (11). The target is found at index 5.
 

This process takes only 3 steps, whereas a linear search would take 6 steps.

Why Binary Search is Efficient

• Reduced Comparisons: Binary search minimizes the number of comparisons by halving the search space each time.
   
• Scalability: As the dataset grows, the number of steps required grows logarithmically, not linearly. This makes binary search ideal for large datasets.

Performance Summary Table

• Time Complexity: Both approaches have O(log n) time complexity, making them efficient for large datasets.
   
• Space Complexity: The recursive approach uses extra space due to function calls (stack space), while the iterative approach runs in constant space (O(1)).

Linear Search vs Binary Search

Key Differences

1. Efficiency: Binary search is significantly faster than linear search for large datasets.
    
2. Sorting Requirement: Binary search requires a sorted array, whereas linear search works on both sorted and unsorted arrays.
    
3. Use Cases: Linear search is simple and useful for small datasets, while binary search is better for performance-critical applications.

Frequently Asked Questions

Why is binary search faster than linear search?

Binary search reduces the search space by half at every step, leading to O(log n) time complexity, whereas linear search checks elements one by one, resulting in O(n) time complexity.

When should I use linear search instead of binary search?

Use linear search when the dataset is small or unsorted. Binary search should be used for large datasets where sorting is feasible.

Can binary search be used on unsorted arrays?

No, binary search requires the array to be sorted. If the array is unsorted, it must be sorted first before applying binary search.

Conclusion

Binary Search in Javascript is an efficient algorithm for searching elements in a sorted array. We learned both recursive and iterative implementations in JavaScript, compared it with linear search, and analyzed its performance. Understanding binary search is essential for coding interviews and optimizing search operations in real-world applications.