Binary Search

Overview

Searches sorted data by comparing with the middle element and reducing the search range each step.

Implementation

• Iterative:

  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) {
        left = mid + 1;
      } else if (arr[mid] > target) {
        right = mid - 1;
      } else {
        return mid;
      }
    }
  
    return false;
  }
  
  console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6

• Recursive:

  function binarySearch(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
      return false;
    }
  
    const mid = Math.floor((left + right) / 2);
  
    if (arr[mid] < target) {
      return binarySearch(arr, target, mid + 1, right);
    } else if (arr[mid] > target) {
      return binarySearch(arr, target, left, mid - 1);
    } else {
      return mid;
    }
  }
  
  console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6