Marauder Bot

Problem

You are given an array of distinct integers already sorted in ascending order, plus a target value. Return the index of the target if it appears in the array, otherwise return -1.

Example. For the array [-1, 0, 3, 5, 9, 12] and a target of 9, the answer is index 4.

Key idea

Checking every element in order takes time proportional to the array size, which throws away the fact that the array is sorted. Comparing the target to the value at the midpoint tells you which half can be discarded entirely: if the target is larger than the middle value, nothing at or before the midpoint can match, and if it is smaller, nothing at or after it can match.

Maintain a low and high boundary spanning the array. Look at the value at the midpoint. If it equals the target, you are done. Otherwise narrow the boundary to whichever half could still contain the target and repeat. Each comparison eliminates roughly half of the remaining candidates, so the range shrinks geometrically, and only a handful of comparisons are needed even for a huge array.

Solution

function search(nums: number[], target: number): number {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    // low + (high - low) / 2 avoids overflow that (low + high) / 2 could hit
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

Complexity

Time: O(log n). Each comparison halves the remaining search space.
Space: O(1). Only the two boundary pointers are kept.

Watch out for

Computing the midpoint as (low + high) / 2 can overflow in languages with fixed-width integers; low + (high - low) / 2 avoids it.
Keep the loop condition and boundary updates consistent, or the search can loop forever or skip the target.
The array must actually be sorted beforehand; binary search on unsorted data gives meaningless results.

Pattern

This is the foundational "halving" search, and the same boundary-narrowing logic extends well beyond finding an exact value: it underlies searching rotated arrays, locating a boundary in a monotonic condition, and binary-searching over an answer space rather than an array index.

Binary Search