Binary Search: Standard & Bisect Boundaries

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Divide and Conquer in O(log N)

Searching an element linearly in an array of 1,000,000 items takes up to 1,000,000 comparisons. Binary Search cuts the search space in half at every step, finding any element in at most 20 comparisons ($log_2(1,000,000) approx 20$)!

2. Standard Binary Search Template

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

  while (left <= right) {
    // Avoid integer overflow: Math.floor(left + (right - left) / 2)
    const mid = Math.floor(left + (right - left) / 2);

    if (nums[mid] === target) {
      return mid; // Found target index!
    } else if (nums[mid] < target) {
      left = mid + 1; // Target is in the right half
    } else {
      right = mid - 1; // Target is in the left half
    }
  }

  return -1; // Target not found
}

console.log(binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23)); // Output: 5

3. Bisect Left (Lower Bound)

Find the first position where target can be inserted while maintaining sorted order:

function bisectLeft(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid; // Narrow right bound
    }
  }

  return left; // First index where nums[index] >= target
}

console.log(bisectLeft([1, 2, 4, 4, 4, 6, 7], 4)); // Output: 2 (First occurrence of 4)

4. Common Mistakes

• Integer Overflow in Mid Calculation: Writing (left + right) / 2 can overflow 32-bit signed integers in languages like Java, C++, and Go when left + right > 2^31 - 1. Use left + (right - left) / 2.
• Infinite Loops from Improper Pointer Updates: Setting left = mid instead of left = mid + 1 can freeze the loop when left and right are adjacent.

5. Next Steps

Binary search applies to any monotonic search space. Next, let's explore Merge Sort and Quick Sort!