function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;  // inclusive bounds

  while (lo <= hi) {  // loop while search space is non-empty
    // Safe midpoint: avoids integer overflow (matters in Java/C, but good habit)
    const mid = lo + Math.floor((hi - lo) / 2);
    // OR: const mid = (lo + hi) >>> 1;  // unsigned right shift, also safe

    if (arr[mid] === target) return mid;   // found!
    if (arr[mid] < target) lo = mid + 1;  // target is to the right
    else hi = mid - 1;                    // target is to the left
  }

  return -1;  // not found
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
binarySearch(arr, 7);   // → 3
binarySearch(arr, 1);   // → 0  (leftmost element)
binarySearch(arr, 19);  // → 9  (rightmost element)
binarySearch(arr, 6);   // → -1 (not present)
binarySearch(arr, 20);  // → -1 (beyond range)

function binarySearchRecursive(arr, target, lo = 0, hi = arr.length - 1) {
  if (lo > hi) return -1;  // base case: search space empty

  const mid = lo + Math.floor((hi - lo) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, hi);
  return binarySearchRecursive(arr, target, lo, mid - 1);
}

// Complexity:
// Time:  O(log n) — halves search space each call
// Space: O(log n) — recursion depth equals number of halvings
// Compare to iterative: O(1) space — prefer iterative for large inputs

// ===== TEMPLATE 1: lo <= hi (inclusive both ends) =====
// Loop exits when lo > hi (search space is empty)
// Always update lo = mid + 1 or hi = mid - 1 (never lo = mid or hi = mid)
function template1(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// ===== TEMPLATE 2: lo < hi (half-open interval [lo, hi)) =====
// Loop exits when lo === hi (one element remains, check it after)
// Can use hi = mid (not mid - 1) because hi is exclusive
function template2(arr, target) {
  let lo = 0, hi = arr.length;   // NOTE: hi = length (exclusive)
  while (lo < hi) {              // NOTE: strict less than
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;               // NOTE: hi = mid, not mid - 1
  }
  // lo === hi: the insertion point
  return lo < arr.length && arr[lo] === target ? lo : -1;
}

// ===== DANGEROUS WRONG VERSION =====
// BUG: lo = mid (not mid + 1) causes infinite loop when lo = hi - 1
function buggySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) lo = mid;  // BUG: should be mid + 1
    else hi = mid;
  }
  return arr[lo] === target ? lo : -1;
  // When lo=0, hi=1: mid=0, if arr[0]<target: lo=0 again → infinite loop!
}

// Returns the leftmost index where target could be inserted (first position >= target)
// Equivalent to C++ lower_bound
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;  // hi = length (target could go at the end)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;  // arr[mid] >= target, so hi = mid
  }
  return lo;  // insertion point
}

// LeetCode 35 — Search Insert Position
function searchInsert(nums, target) {
  return lowerBound(nums, target);
}

const arr = [1, 3, 5, 7, 9];
lowerBound(arr, 5);   // → 2 (arr[2] = 5, exact match)
lowerBound(arr, 4);   // → 2 (insert between 3 and 5)
lowerBound(arr, 0);   // → 0 (insert before everything)
lowerBound(arr, 10);  // → 5 (insert after everything)

// LeetCode 33 — Search in Rotated Sorted Array
function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {
      // Left half [lo..mid] is sorted
      if (nums[lo] <= target && target < nums[mid]) {
        hi = mid - 1;  // target is in the sorted left half
      } else {
        lo = mid + 1;  // target is in the right half
      }
    } else {
      // Right half [mid..hi] is sorted
      if (nums[mid] < target && target <= nums[hi]) {
        lo = mid + 1;  // target is in the sorted right half
      } else {
        hi = mid - 1;  // target is in the left half
      }
    }
  }
  return -1;
}

searchRotated([4,5,6,7,0,1,2], 0);  // → 4
searchRotated([4,5,6,7,0,1,2], 3);  // → -1
searchRotated([1], 0);               // → -1

// Universal template: find the leftmost position where condition(x) is true
// Requires: condition is false for all x < answer, true for all x >= answer
function binarySearchAnswer(lo, hi, condition) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (condition(mid)) hi = mid;      // mid might be the answer, don't exclude it
    else lo = mid + 1;                 // mid definitely not the answer
  }
  return lo;  // lo === hi: the answer
}

// Example: find first index where arr[index] >= target
function firstGreaterEqual(arr, target) {
  return binarySearchAnswer(0, arr.length, mid => arr[mid] >= target);
}

// Example: find square root (integer floor)
function mySqrt(x) {
  if (x < 2) return x;
  // Find largest k where k² <= x
  return binarySearchAnswer(1, x, mid => mid * mid > x) - 1;
}

mySqrt(8);   // → 2  (2²=4 ≤ 8, 3²=9 > 8)
mySqrt(9);   // → 3  (3²=9 ≤ 9)