JavaScript Binary Search Implementation

Here's a concise explanation of binary search in JavaScript, along with an example implementation.

What is Binary Search?

Binary search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, it searches the left half; if it's greater, it searches the right half. This process continues until the target value is found or the interval is empty.

Binary Search Algorithm Steps

1. Initialize two pointers, left and right, to the start and end of the array.
2. Calculate the mid index as the average of left and right.
3. Compare the middle element with the target:
   • If they are equal, return the mid index.
   • If the target is less than the middle element, move the right pointer to mid - 1.
   • If the target is greater, move the left pointer to mid + 1.
4. Repeat steps 2-3 until the target is found or the pointers cross.

1 function binarySearch(arr, target) {
2     let left = 0;
3     let right = arr.length - 1;
4 
5     while (left <= right) {
6         const mid = Math.floor((left + right) / 2);
7 
8         if (arr[mid] === target) {
9             return mid; // Target found
10         }
11         if (arr[mid] < target) {
12             left = mid + 1; // Search right half
13         } else {
14             right = mid - 1; // Search left half
15         }
16     }
17 
18     return -1; // Target not found
19 }
20 
21 // Example usage:
22 const sortedArray = [1, 3, 5, 7, 9, 11, 13];
23 const target = 7;
24 const result = binarySearch(sortedArray, target);
25 
26 console.log(result); // Output: 3 (index of the target)

This implementation provides a time complexity of $𝑂(log 𝑛)$, making it much more efficient than a linear search for large datasets.