A binary search algorithm in JavaScript is used to efficiently...

A binary search algorithm in JavaScript is used to efficiently find the position of a target value in a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search focuses on the lower half of the array; if the target value is greater, the search focuses on the upper half. This process continues until the target value is found or the search range is exhausted.

Here is an example binary search implementation in JavaScript:

function binarySearch(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; // Target value found at index `mid`
        } else if (arr[mid] < target) {
            left = mid + 1; // Narrow search to the right side
        } else {
            right = mid - 1; // Narrow search to the left side
        }
    }
    
    return -1; // Target value not found
}

What does this code do?

1. The function takes in:

   • arr: A sorted array to search through.
   • target: The value to be found in the array.

2. It initializes two pointers, left and right, which define the range of the search:

   • left starts at the beginning of the array.
   • right starts at the end of the array.

3. While left is less than or equal to right:

   • It calculates the middle index (mid) of the current search range.
   • It compares the middle element (arr[mid]) to the target.
     • If they match, it returns the index of the mid.
     • If the middle element is smaller than the target, it moves the left pointer up (mid + 1) to discard the lower half of the range.
     • If the middle element is greater than the target, it moves the right pointer down (mid - 1) to discard the upper half of the range.

4. If the search range runs out (i.e., left becomes greater than right), the function returns -1 to indicate that the target value is not present in the array.

Example Usage:

const sortedArray = [1, 3, 5, 7, 9, 11];
const target = 7;

const index = binarySearch(sortedArray, target);
console.log(index); // Output: 3 (since 7 is at index 3 in the array)

Efficiency:

• Time Complexity: O(log n) — The array is halved on each iteration, making it very efficient.
• Space Complexity: O(1) — Uses constant extra space.

This code is widely used to perform quick lookups in sorted datasets!