Binary Search

// 1) Classic — find target index, return -1 if missing
function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = lo + ((hi - lo) >> 1);   // overflow-safe + integer
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return -1;
}

// 2) Find the leftmost (first) occurrence — lower_bound
function lowerBound(arr, target) {
    let lo = 0, hi = arr.length;             // half-open
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid;
    }
    return lo;  // index of first element >= target (could be arr.length)
}

// 3) Find the rightmost — upper_bound
function upperBound(arr, target) {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (arr[mid] <= target) lo = mid + 1;
        else                    hi = mid;
    }
    return lo;  // index of first element > target
}

// Count occurrences
const count = upperBound(arr, t) - lowerBound(arr, t);

// 4) Rotated sorted array — find target in [4,5,6,7,0,1,2]
function searchRotated(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (arr[mid] === target) return mid;
        if (arr[lo] <= arr[mid]) {           // left half sorted
            if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                              // right half sorted
            if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

// 5) Find peak element (any local max)
function findPeak(arr) {
    let lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (arr[mid] < arr[mid + 1]) lo = mid + 1;
        else                          hi = mid;
    }
    return lo;
}

// 6) Search the ANSWER space — binary-search on a value, not an index
// Find the smallest capacity for shipping `weights` within D days
function shipCapacity(weights, D) {
    let lo = Math.max(...weights);
    let hi = weights.reduce((a, b) => a + b, 0);
    while (lo < hi) {
        const cap = lo + ((hi - lo) >> 1);
        if (feasible(weights, D, cap)) hi = cap;
        else                            lo = cap + 1;
    }
    return lo;
}
function feasible(weights, D, cap) {
    let days = 1, load = 0;
    for (const w of weights) {
        if (load + w > cap) { days++; load = 0; }
        load += w;
    }
    return days <= D;
}

// 7) Search in 2D matrix (row + col sorted)
function search2D(m, target) {
    let r = 0, c = m[0].length - 1;
    while (r < m.length && c >= 0) {
        if (m[r][c] === target) return [r, c];
        if (m[r][c] > target)   c--;
        else                    r++;
    }
    return null;
}

// 8) Python — bisect module
# import bisect
# i = bisect.bisect_left(arr, target)      # lower_bound
# i = bisect.bisect_right(arr, target)     # upper_bound
# bisect.insort(arr, x)                    # insert keeping sorted

// 9) Common bugs
//   • mid = (lo + hi) / 2 → overflow on int_max sized arrays. Use lo + (hi - lo) / 2.
//   • Off-by-one: <= vs <  bounds. Decide closed [lo, hi] or half-open [lo, hi) — stick with it.
//   • Infinite loop when lo doesn't progress — ensure each branch shrinks the range.
//   • Floating-point binary search — use a fixed iteration count, not termination by equality.

// 10) When binary search is the right tool
//   • Sorted data (obviously)
//   • You can express a monotonic predicate on the index/value
//   • You're searching the ANSWER space (min cost, min capacity, max value satisfying X)
//   • You can transform an O(n) check into a yes/no question

function search(nums, target) {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const m = (lo + hi) >> 1;
        if (nums[m] === target) return m;
        if (nums[m] < target) lo = m + 1; else hi = m - 1;
    }
    return -1;
}