//grind75
← Back

Binary Search

Halve the search space each step to find a value in a sorted array in O(log n).

Theory → 1 / 1
func binarySearch(nums []int, target int) int {

}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid

        // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid

        // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        case nums[mid] < target:
            lo = mid + 1
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid

        // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        case nums[mid] < target:
            lo = mid + 1

        // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid

        // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        case nums[mid] < target:
            lo = mid + 1

        // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
        default:
            hi = mid - 1
        }
    }
}
func binarySearch(nums []int, target int) int {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi := 0, len(nums)-1

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    for lo <= hi {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid := lo + (hi-lo)/2

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        switch {
        // 1) Direct hit — mid is the index we're after.
        case nums[mid] == target:
            return mid

        // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        case nums[mid] < target:
            lo = mid + 1

        // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
        default:
            hi = mid - 1
        }
    }

    return -1 // window emptied: not found. O(log n)
}
def binary_search(nums, target):
    pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            pass
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
            # 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
        elif nums[mid] < target:
            # 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
        elif nums[mid] < target:
            # 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1
            # 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
        elif nums[mid] < target:
            # 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1
        else:
            # 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            hi = mid - 1
def binary_search(nums, target):
    # Track the still-possible window [lo, hi], inclusive on both ends.
    lo, hi = 0, len(nums) - 1

    # Loop while the window is non-empty. Use <= because hi is inclusive.
    while lo <= hi:
        # Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        mid = lo + (hi - lo) // 2

        # Compare the middle to target — three outcomes. Always exclude mid when
        # narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if nums[mid] == target:
            # 1) Direct hit — mid is the index we're after.
            return mid
        elif nums[mid] < target:
            # 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1
        else:
            # 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            hi = mid - 1

    return -1  # window emptied: not found. O(log n)
function binarySearch(nums, target) {

}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    } else {
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
      hi = mid - 1;
    }
  }
}
function binarySearch(nums, target) {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    } else {
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
      hi = mid - 1;
    }
  }

  return -1; // window emptied: not found. O(log n)
}
function binarySearch(nums: number[], target: number): number {

}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    } else {
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
      hi = mid - 1;
    }
  }
}
function binarySearch(nums: number[], target: number): number {
  // Track the still-possible window [lo, hi], inclusive on both ends.
  let lo = 0, hi = nums.length - 1;

  // Loop while the window is non-empty. Use <= because hi is inclusive.
  while (lo <= hi) {
    // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    const mid = lo + Math.floor((hi - lo) / 2);

    // Compare the middle to target — three outcomes. Always exclude mid when
    // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    if (nums[mid] === target) {
      // 1) Direct hit — mid is the index we're after.
      return mid;
    } else if (nums[mid] < target) {
      // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
      lo = mid + 1;
    } else {
      // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
      hi = mid - 1;
    }
  }

  return -1; // window emptied: not found. O(log n)
}
class Solution {
    public int binarySearch(int[] nums, int target) {

    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }
    }
}
class Solution {
    public int binarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }

        return -1; // window emptied: not found. O(log n)
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {

    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }
    }
}
public class Solution {
    public int BinarySearch(int[] nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = nums.Length - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }

        return -1; // window emptied: not found. O(log n)
    }
}
int binarySearch(int* nums, int numsSize, int target) {

}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
            // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
        } else if (nums[mid] < target) {
            // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1;
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
        } else if (nums[mid] < target) {
            // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1;
            // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
        } else if (nums[mid] < target) {
            // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1;
        } else {
            // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            hi = mid - 1;
        }
    }
}
int binarySearch(int* nums, int numsSize, int target) {
    // Track the still-possible window [lo, hi], inclusive on both ends.
    int lo = 0, hi = numsSize - 1;

    // Loop while the window is non-empty. Use <= because hi is inclusive.
    while (lo <= hi) {
        // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        int mid = lo + (hi - lo) / 2;

        // Compare the middle to target — three outcomes. Always exclude mid when
        // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        if (nums[mid] == target) {
            // 1) Direct hit — mid is the index we're after.
            return mid;
        } else if (nums[mid] < target) {
            // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            lo = mid + 1;
        } else {
            // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            hi = mid - 1;
        }
    }

    return -1; // window emptied: not found. O(log n)
}
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {

    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }
    }
};
#include <vector>
using namespace std;

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        // Track the still-possible window [lo, hi], inclusive on both ends.
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop while the window is non-empty. Use <= because hi is inclusive.
        while (lo <= hi) {
            // Overflow-safe midpoint: lo+(hi-lo)/2, not (lo+hi)/2.
            int mid = lo + (hi - lo) / 2;

            // Compare the middle to target — three outcomes. Always exclude mid when
            // narrowing (mid+1 / mid-1) so the window keeps shrinking.
            if (nums[mid] == target) {
                // 1) Direct hit — mid is the index we're after.
                return mid;
            } else if (nums[mid] < target) {
                // 2) Middle too small — the answer is to the RIGHT, so move lo past mid.
                lo = mid + 1;
            } else {
                // 3) Otherwise middle too big — the answer is to the LEFT, so move hi past mid.
                hi = mid - 1;
            }
        }

        return -1; // window emptied: not found. O(log n)
    }
};

Tap the left half to go back, the right half to go forward.

Arrow keys or space to navigate · Esc to exit.