Binary Search

Binary Search is an efficient algorithm used to find a specific value in a sorted array or list. It works by repeatedly dividing the search interval in half until the desired value is found or the end of the collection is reached.

This algorithm requires the data to be sorted, which makes it less flexible in some situations. However, it is much more efficient for large datasets compared to linear search.

How It Works

Binary Search works by repeatedly cutting the search range in half:

Start with the entire sorted array.
Find the middle element.
Compare the middle element to the target value.
If they match, return the index.
If the target is smaller, search the left half.
If the target is larger, search the right half.
Repeat until the value is found or the range is empty.

If the value is not found, the algorithm returns -1.

By halving the search space each time, Binary Search is significantly more efficient than checking every element.

JavaScript Example


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;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// Example usage
const values = [3, 7, 12, 19, 25, 31];

console.log(binarySearch(values, 19)); // 3
console.log(binarySearch(values, 8));  // -1