Complete Guide to Binary Search in JavaScript

Note : https://gist.github.com/carefree-ladka/58c72ce26f079ffea973bbd2e1dec60e

Table of Contents

1. Introduction to Binary Search
2. Basic Binary Search
3. Lower Bound and Upper Bound
   • Lower Bound (First Occurrence)
   • Upper Bound (Last Occurrence)
4. Binary Search on Rotated Arrays
   • Search in Rotated Sorted Array
   • Find Minimum in Rotated Array
   • Find Maximum in Rotated Array
5. Peak Finding
   • Peak Element in Array
   • Peak in Mountain Array
6. Binary Search on Answer
   • Concept and When to Use
   • Common Patterns
7. Binary Search in 2D Matrix
   • Row-wise and Column-wise Sorted
   • Fully Sorted Matrix
8. Binary Search with Precision
   • Square Root with Precision
   • Finding Real Number Answers
9. Advanced Patterns
10. Time and Space Complexity
11. Common Pitfalls and Best Practices

---

Introduction to Binary Search {#introduction}

Binary Search is a highly efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, achieving O(log n) time complexity.

Key Requirements:

• Array must be sorted (or have some monotonic property)
• Random access to elements (array/list structure)

Core Concept: Instead of checking every element linearly, we eliminate half of the remaining elements at each step by comparing with the middle element.

---

Basic Binary Search {#basic-binary-search}

The fundamental binary search implementation to find if a target exists in a sorted array.

/**
 * Basic Binary Search - Find target in sorted array
 * @param {number[]} arr - Sorted array
 * @param {number} target - Element to find
 * @return {number} - Index of target, or -1 if not found
 */
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        // Prevent integer overflow: use Math.floor((left + right) / 2)
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Target not found
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr, 7));  // Output: 3
console.log(binarySearch(arr, 6));  // Output: -1

Recursive Implementation:

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1;
    }
    
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

---

Lower Bound and Upper Bound {#lower-and-upper-bound}

Lower Bound (First Occurrence) {#lower-bound}

Finds the first position where we can insert the target while maintaining sorted order, or the first occurrence of the target.

/**
 * Lower Bound - Find first position >= target
 * @param {number[]} arr - Sorted array
 * @param {number} target - Target value
 * @return {number} - Index of lower bound
 */
function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid; // Could be the answer, keep searching left
        }
    }
    
    return left;
}

// Find first occurrence of target
function findFirstOccurrence(arr, target) {
    const idx = lowerBound(arr, target);
    return (idx < arr.length && arr[idx] === target) ? idx : -1;
}

// Example
const arr1 = [1, 2, 2, 2, 3, 4, 5];
console.log(lowerBound(arr1, 2));           // Output: 1 (first occurrence)
console.log(findFirstOccurrence(arr1, 2));  // Output: 1
console.log(lowerBound(arr1, 6));           // Output: 7 (insertion point)

Upper Bound (Last Occurrence) {#upper-bound}

Finds the last position where the target can exist, or the position after the last occurrence.

/**
 * Upper Bound - Find first position > target
 * @param {number[]} arr - Sorted array
 * @param {number} target - Target value
 * @return {number} - Index of upper bound
 */
function upperBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// Find last occurrence of target
function findLastOccurrence(arr, target) {
    const idx = upperBound(arr, target) - 1;
    return (idx >= 0 && arr[idx] === target) ? idx : -1;
}

// Count occurrences using bounds
function countOccurrences(arr, target) {
    const first = lowerBound(arr, target);
    const last = upperBound(arr, target);
    return last - first;
}

// Example
const arr2 = [1, 2, 2, 2, 3, 4, 5];
console.log(upperBound(arr2, 2));           // Output: 4
console.log(findLastOccurrence(arr2, 2));   // Output: 3
console.log(countOccurrences(arr2, 2));     // Output: 3

---

Binary Search on Rotated Arrays {#rotated-arrays}

Search in Rotated Sorted Array {#search-rotated}

A sorted array that has been rotated at some pivot point.

/**
 * Search in Rotated Sorted Array
 * @param {number[]} nums - Rotated sorted array
 * @param {number} target - Target to find
 * @return {number} - Index of target or -1
 */
function searchRotated(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

// Example
const rotated = [4, 5, 6, 7, 0, 1, 2];
console.log(searchRotated(rotated, 0));  // Output: 4
console.log(searchRotated(rotated, 3));  // Output: -1

Find Minimum in Rotated Array {#find-minimum-rotated}

/**
 * Find Minimum in Rotated Sorted Array
 * @param {number[]} nums - Rotated sorted array
 * @return {number} - Minimum element
 */
function findMinRotated(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // If mid element is greater than right, minimum is in right half
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            // Minimum is in left half (including mid)
            right = mid;
        }
    }
    
    return nums[left];
}

// Example
console.log(findMinRotated([4, 5, 6, 7, 0, 1, 2]));  // Output: 0
console.log(findMinRotated([3, 4, 5, 1, 2]));        // Output: 1

Find Maximum in Rotated Array {#find-maximum-rotated}

/**
 * Find Maximum in Rotated Sorted Array
 * @param {number[]} nums - Rotated sorted array
 * @return {number} - Maximum element
 */
function findMaxRotated(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // If mid is greater than right, max could be at mid or left
        if (nums[mid] > nums[right]) {
            left = mid;
            // Need to break if left and right are adjacent
            if (right - left === 1) break;
        } else {
            right = mid - 1;
        }
    }
    
    return nums[left];
}

// Example
console.log(findMaxRotated([4, 5, 6, 7, 0, 1, 2]));  // Output: 7

---

Peak Finding {#peak-finding}

Peak Element in Array {#peak-element}

A peak element is an element that is strictly greater than its neighbors.

/**
 * Find Peak Element
 * @param {number[]} nums - Array of numbers
 * @return {number} - Index of peak element
 */
function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // If middle element is less than next, peak is on right
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            // Peak is on left (including mid)
            right = mid;
        }
    }
    
    return left;
}

// Example
console.log(findPeakElement([1, 2, 3, 1]));        // Output: 2
console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // Output: 5

Peak in Mountain Array {#mountain-peak}

A mountain array increases up to a peak and then decreases.

/**
 * Find Peak in Mountain Array
 * @param {number[]} arr - Mountain array
 * @return {number} - Index of peak
 */
function peakIndexInMountainArray(arr) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < arr[mid + 1]) {
            // Ascending, peak is to the right
            left = mid + 1;
        } else {
            // Descending, peak is to the left (or at mid)
            right = mid;
        }
    }
    
    return left;
}

// Search in Mountain Array
function searchInMountain(arr, target) {
    const peak = peakIndexInMountainArray(arr);
    
    // Search in ascending part
    let result = binarySearch(arr.slice(0, peak + 1), target);
    if (result !== -1) return result;
    
    // Search in descending part (reverse binary search)
    let left = peak + 1;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            right = mid - 1; // Reversed because descending
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

// Example
console.log(peakIndexInMountainArray([0, 1, 0]));        // Output: 1
console.log(peakIndexInMountainArray([0, 2, 1, 0]));     // Output: 1
console.log(peakIndexInMountainArray([0, 10, 5, 2]));    // Output: 1

---

Binary Search on Answer {#binary-search-on-answer}

Concept and When to Use {#bs-answer-concept}

Binary search on answer is used when:

• The answer lies in a range [min, max]
• We can check if a particular value is valid in O(n) or better
• If answer x is valid, then all values in one direction are also valid (monotonic property)

Pattern:

1. Define the search space (min and max possible answer)
2. Write a check function to validate if a value works
3. Binary search on the range to find optimal answer

Common Patterns {#bs-answer-patterns}

1. Minimum Capacity / Maximum Minimum

/**
 * Split Array Largest Sum
 * Split array into m subarrays to minimize the largest sum
 * @param {number[]} nums - Array of numbers
 * @param {number} m - Number of subarrays
 * @return {number} - Minimum largest sum
 */
function splitArray(nums, m) {
    // Check if we can split with max subarray sum <= maxSum
    function canSplit(maxSum) {
        let count = 1;
        let currentSum = 0;
        
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > m) return false;
            } else {
                currentSum += num;
            }
        }
        
        return true;
    }
    
    let left = Math.max(...nums);  // Minimum possible answer
    let right = nums.reduce((a, b) => a + b, 0);  // Maximum possible answer
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (canSplit(mid)) {
            right = mid;  // Try smaller maximum
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example
console.log(splitArray([7, 2, 5, 10, 8], 2));  // Output: 18

2. Koko Eating Bananas

/**
 * Minimum eating speed to finish all bananas in h hours
 * @param {number[]} piles - Banana piles
 * @param {number} h - Hours available
 * @return {number} - Minimum eating speed
 */
function minEatingSpeed(piles, h) {
    function canFinish(speed) {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / speed);
        }
        return hours <= h;
    }
    
    let left = 1;
    let right = Math.max(...piles);
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (canFinish(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example
console.log(minEatingSpeed([3, 6, 7, 11], 8));  // Output: 4

3. Allocate Books / Painter's Partition

/**
 * Allocate minimum pages to students
 * @param {number[]} books - Pages in each book
 * @param {number} students - Number of students
 * @return {number} - Minimum maximum pages
 */
function allocateBooks(books, students) {
    if (students > books.length) return -1;
    
    function isValid(maxPages) {
        let studentCount = 1;
        let currentPages = 0;
        
        for (const pages of books) {
            if (pages > maxPages) return false;
            
            if (currentPages + pages > maxPages) {
                studentCount++;
                currentPages = pages;
                
                if (studentCount > students) return false;
            } else {
                currentPages += pages;
            }
        }
        
        return true;
    }
    
    let left = Math.max(...books);
    let right = books.reduce((a, b) => a + b, 0);
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (isValid(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

// Example
console.log(allocateBooks([12, 34, 67, 90], 2));  // Output: 113

4. Find Kth Smallest in Sorted Matrix

/**
 * Kth Smallest Element in Sorted Matrix
 * @param {number[][]} matrix - n x n matrix sorted row and column wise
 * @param {number} k - Find kth smallest
 * @return {number} - Kth smallest element
 */
function kthSmallest(matrix, k) {
    const n = matrix.length;
    
    function countLessEqual(mid) {
        let count = 0;
        let col = n - 1;
        
        for (let row = 0; row < n; row++) {
            while (col >= 0 && matrix[row][col] > mid) {
                col--;
            }
            count += (col + 1);
        }
        
        return count;
    }
    
    let left = matrix[0][0];
    let right = matrix[n - 1][n - 1];
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (countLessEqual(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// Example
const matrix = [
    [1,  5,  9],
    [10, 11, 13],
    [12, 13, 15]
];
console.log(kthSmallest(matrix, 8));  // Output: 13

---

Binary Search in 2D Matrix {#matrix-search}

Row-wise and Column-wise Sorted {#matrix-row-col-sorted}

/**
 * Search in row-wise and column-wise sorted matrix
 * @param {number[][]} matrix - Sorted matrix
 * @param {number} target - Target to find
 * @return {boolean} - True if found
 */
function searchMatrix2D(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;
    
    let row = 0;
    let col = matrix[0].length - 1;
    
    // Start from top-right corner
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--; // Move left
        } else {
            row++; // Move down
        }
    }
    
    return false;
}

// Example
const matrix1 = [
    [1,  4,  7, 11, 15],
    [2,  5,  8, 12, 19],
    [3,  6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
];
console.log(searchMatrix2D(matrix1, 5));   // Output: true
console.log(searchMatrix2D(matrix1, 20));  // Output: false

Fully Sorted Matrix {#matrix-fully-sorted}

When the matrix is fully sorted (each row is sorted, and first element of next row is greater than last element of previous row).

/**
 * Search in fully sorted matrix (treat as 1D array)
 * @param {number[][]} matrix - Fully sorted matrix
 * @param {number} target - Target to find
 * @return {boolean} - True if found
 */
function searchFullySortedMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;
    
    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // Convert 1D index to 2D coordinates
        const row = Math.floor(mid / n);
        const col = mid % n;
        const midVal = matrix[row][col];
        
        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

// Example
const matrix2 = [
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
];
console.log(searchFullySortedMatrix(matrix2, 3));   // Output: true
console.log(searchFullySortedMatrix(matrix2, 13));  // Output: false

---

Binary Search with Precision {#precision-search}

Square Root with Precision {#sqrt-precision}

/**
 * Calculate square root with given precision
 * @param {number} n - Number to find square root of
 * @param {number} precision - Decimal places
 * @return {number} - Square root
 */
function sqrtWithPrecision(n, precision = 6) {
    if (n < 0) return NaN;
    if (n === 0 || n === 1) return n;
    
    let left = 0;
    let right = n;
    const epsilon = Math.pow(10, -precision);
    
    while (right - left > epsilon) {
        const mid = (left + right) / 2;
        const square = mid * mid;
        
        if (Math.abs(square - n) < epsilon) {
            return parseFloat(mid.toFixed(precision));
        } else if (square < n) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return parseFloat(((left + right) / 2).toFixed(precision));
}

// Integer part first, then precision
function sqrtOptimized(n, precision = 6) {
    if (n < 0) return NaN;
    if (n === 0 || n === 1) return n;
    
    // Find integer part using binary search
    let left = 0;
    let right = n;
    let intPart = 0;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (mid * mid === n) {
            return mid;
        } else if (mid * mid < n) {
            intPart = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Find decimal part
    let answer = intPart;
    let increment = 0.1;
    
    for (let i = 0; i < precision; i++) {
        while (answer * answer <= n) {
            answer += increment;
        }
        answer -= increment;
        increment /= 10;
    }
    
    return parseFloat(answer.toFixed(precision));
}

// Examples
console.log(sqrtWithPrecision(50, 4));      // Output: 7.0711
console.log(sqrtOptimized(2, 6));           // Output: 1.414214
console.log(sqrtOptimized(10, 3));          // Output: 3.162

Finding Real Number Answers {#real-number-search}

/**
 * Find cube root with precision
 * @param {number} n - Number
 * @param {number} precision - Decimal places
 * @return {number} - Cube root
 */
function cubeRoot(n, precision = 6) {
    let left = n < 0 ? n : 0;
    let right = n < 0 ? 0 : n;
    
    if (n > -1 && n < 1) {
        left = -1;
        right = 1;
    }
    
    const epsilon = Math.pow(10, -precision);
    
    while (right - left > epsilon) {
        const mid = (left + right) / 2;
        const cube = mid * mid * mid;
        
        if (Math.abs(cube - n) < epsilon) {
            return parseFloat(mid.toFixed(precision));
        } else if (cube < n) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return parseFloat(((left + right) / 2).toFixed(precision));
}

// Example
console.log(cubeRoot(27, 4));    // Output: 3.0000
console.log(cubeRoot(8, 6));     // Output: 2.000000
console.log(cubeRoot(-27, 4));   // Output: -3.0000

---

Advanced Patterns {#advanced-patterns}

Median of Two Sorted Arrays

/**
 * Find median of two sorted arrays
 * @param {number[]} nums1 - First sorted array
 * @param {number[]} nums2 - Second sorted array
 * @return {number} - Median
 */
function findMedianSortedArrays(nums1, nums2) {
    // Ensure nums1 is smaller for optimization
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    
    const m = nums1.length;
    const n = nums2.length;
    let left = 0;
    let right = m;
    
    while (left <= right) {
        const partition1 = Math.floor((left + right) / 2);
        const partition2 = Math.floor((m + n + 1) / 2) - partition1;
        
        const maxLeft1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
        const minRight1 = partition1 === m ? Infinity : nums1[partition1];
        
        const maxLeft2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
        const minRight2 = partition2 === n ? Infinity : nums2[partition2];
        
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            // Found the correct partition
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }
    
    throw new Error("Arrays are not sorted");
}

// Example
console.log(findMedianSortedArrays([1, 3], [2]));        // Output: 2
console.log(findMedianSortedArrays([1, 2], [3, 4]));     // Output: 2.5

Capacity To Ship Packages Within D Days

/**
 * Minimum capacity to ship packages in given days
 * @param {number[]} weights - Package weights
 * @param {number} days - Days available
 * @return {number} - Minimum ship capacity
 */
function shipWithinDays(weights, days) {
    function canShip(capacity) {
        let daysNeeded = 1;
        let currentWeight = 0;
        
        for (const weight of weights) {
            if (currentWeight + weight > capacity) {
                daysNeeded++;
                currentWeight = weight;
                
                if (daysNeeded > days) return false;
            } else {
                currentWeight += weight;
            }
        }
        
        return true;
    }
    
    let left = Math.max(...weights);
    let right = weights.reduce((a, b) => a + b, 0);
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (canShip(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example
console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));  // Output: 15

Find K Closest Elements

/**
 * Find k closest elements to x
 * @param {number[]} arr - Sorted array
 * @param {number} k - Number of elements
 * @param {number} x - Target value
 * @return {number[]} - K closest elements
 */
function findClosestElements(arr, k, x) {
    let left = 0;
    let right = arr.length - k;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // Compare distances: which window is better?
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return arr.slice(left, left + k);
}

// Example
console.log(findClosestElements([1, 2, 3, 4, 5], 4, 3));  // Output: [1, 2, 3, 4]
console.log(findClosestElements([1, 2, 3, 4, 5], 4, -1)); // Output: [1, 2, 3, 4]

---

Time and Space Complexity {#complexity}

Time Complexity

Operation	Time Complexity	Notes
Basic Binary Search	O(log n)	Halves search space each iteration
Rotated Array Search	O(log n)	Still divides space in half
2D Matrix Search	O(m + n) or O(log(m*n))	Depends on approach
Binary Search on Answer	O(n * log(range))	n for validation, log for search
Precision Search	O(log(n/ε))	ε is precision

Space Complexity

Implementation	Space Complexity	Notes
Iterative	O(1)	Constant extra space
Recursive	O(log n)	Call stack depth
With auxiliary structures	O(n)	Depends on data structures used

Why Binary Search is Efficient

For an array of size n:

• Linear Search: n comparisons in worst case
• Binary Search: log₂(n) comparisons in worst case

Example:

• Array size: 1,000,000
• Linear Search: Up to 1,000,000 comparisons
• Binary Search: Maximum 20 comparisons (log₂(1,000,000) ≈ 20)

---

Common Pitfalls and Best Practices {#pitfalls}

1. Integer Overflow

Problem:

// Bad: Can overflow for large numbers
const mid = Math.floor((left + right) / 2);

Solution:

// Good: Prevents overflow
const mid = Math.floor(left + (right - left) / 2);

2. Infinite Loops

Problem:

// Can cause infinite loop when left and right are adjacent
while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (condition) {
        left = mid;  // Dangerous!
    } else {
        right = mid - 1;
    }
}

Solution:

// Option 1: Use left + 1 for mid
const mid = Math.floor(left + (right - left + 1) / 2);

// Option 2: Ensure progress
if (condition) {
    left = mid + 1;
} else {
    right = mid;
}

3. Boundary Conditions

Always check:

• Empty array
• Single element array
• Target at boundaries (first/last element)
• Target not in array

function safeBinarySearch(arr, target) {
    // Handle edge cases
    if (!arr || arr.length === 0) return -1;
    if (arr.length === 1) return arr[0] === target ? 0 : -1;
    
    let left = 0;
    let right = arr.length - 1;
    
    // Rest of implementation...
}

4. Loop Condition: < vs <=

// Use left <= right when you want to check every element
while (left <= right) {
    // ...
}

// Use left < right when you want to find boundary/position
while (left < right) {
    // ...
}

5. Search Space Definition

For finding exact match:

let left = 0;
let right = arr.length - 1;  // Inclusive
while (left <= right) { /* ... */ }

For finding boundary/position:

let left = 0;
let right = arr.length;  // Exclusive
while (left < right) { /* ... */ }

6. Monotonicity Check

Before applying binary search, ensure the property you're searching on is monotonic:

// Good: Array is sorted
const sorted = [1, 2, 3, 4, 5];

// Bad: Not monotonic, binary search won't work
const notSorted = [1, 3, 2, 4, 5];

// Good: Function is monotonic (checking feasibility)
function canFinishInTime(time) {
    // Returns true for all times >= minimum
    // Returns false for all times < minimum
}

7. Testing Checklist

Always test your binary search with:

• [ ] Empty array
• [ ] Single element
• [ ] Two elements
• [ ] Target at start
• [ ] Target at end
• [ ] Target in middle
• [ ] Target not present
• [ ] Duplicate elements (if applicable)
• [ ] All same elements (if applicable)

Best Practices Summary

1. Always prevent integer overflow in mid calculation
2. Clearly define search space boundaries (inclusive/exclusive)
3. Use appropriate loop condition (<= vs <)
4. Test edge cases thoroughly
5. Document your invariants (what remains true after each iteration)
6. Verify monotonicity before applying binary search
7. Choose iterative over recursive for space efficiency
8. Use meaningful variable names (left/right instead of i/j)

---

Summary

Binary Search is a powerful technique that extends far beyond simple array searching:

Core Concepts:

• Requires sorted/monotonic property
• O(log n) time complexity
• Can be applied to answer spaces, not just arrays

Key Patterns:

1. Basic Search: Find exact element
2. Bounds: Lower/upper bound for insertions
3. Rotated Arrays: Handle sorted but rotated data
4. Peaks: Find local maxima
5. Answer Search: Optimize over a range of answers
6. 2D Search: Extend to matrices
7. Precision: Handle floating-point searches

When to Use Binary Search:

• Data is sorted or has monotonic property
• Need O(log n) complexity
• Can validate answers efficiently
• Search space is bounded and ordered

Practice Problems:

• LeetCode: 704, 35, 33, 34, 162, 410, 875, 1011, 74, 378
• Focus on understanding the pattern, not memorizing solutions

Master these patterns, and you'll be able to recognize and solve binary search problems efficiently!