Binary Search - Intro & Implementation

Introduction

Binary search is a fundamental and highly efficient algorithm used to search for an element in a sorted array or list. It follows the principle of divide and conquer to rapidly locate the target element. In this guide, we'll introduce the binary search algorithm and provide a step-by-step implementation in JavaScript.

How Binary Search Works

Binary search works by repeatedly dividing the search interval in half. It begins with the entire sorted array and compares the middle element to the target element. If the middle element matches the target, the search is successful. If the middle element is greater than the target, the search continues in the left half of the array, and if it's smaller, the search moves to the right half. This process repeats until the target is found or the search interval becomes empty.

Algorithm Steps

1. Initialize two pointers, left and right, to the start and end of the array, respectively.
2. Calculate the middle index as (left + right) / 2.
3. Compare the middle element with the target:
   • If they match, the search is successful; return the middle index.
   • If the middle element is greater than the target, update right to middle - 1 to search the left half.
   • If the middle element is smaller than the target, update left to middle + 1 to search the right half.
4. Repeat steps 2-3 until the target is found or left becomes greater than right, indicating the target is not in the array.

JavaScript Implementation

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

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

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

  return -1; // Target not found
}

// Example usage:
const sortedArray = [2, 4, 6, 8, 10, 12, 14];
const target = 10;
const result = binarySearch(sortedArray, target);
if (result !== -1) {
  console.log(`Target ${target} found at index ${result}.`);
} else {
  console.log(`Target ${target} not found in the array.`);
}

Time Complexity

Binary search has a time complexity of O(log n), where n is the number of elements in the sorted array. This makes it highly efficient, especially for large datasets, as it divides the search space in half with each comparison.

Conclusion

Binary search is a powerful algorithm for quickly finding elements in a sorted array. Its efficiency makes it a fundamental tool in computer science and is widely used in various applications, including searching, data retrieval, and more. Understanding binary search and its implementation is essential for any programmer or software developer.