Binary Search crash course ↗ · 25

704. Binary Search

Given a sorted array, find a target in O(log n) by repeatedly halving the search space. The canonical lo/hitemplate — with its inclusive bounds and overflow-safe midpoint — anchors every binary-search variant you'll ever write.

● EasyBinary SearchTwo PointersTypeScript

PROBLEM What we're solving

Given a sorted integer array nums and an integer target, return the index of target if it exists, or -1 if it does not. For example: nums=[-1,0,3,5,9,12], target=9 → the answer is 4 (0-indexed). And nums=[-1,0,3,5,9,12], target=2 → -1 (not present). You may not use any built-in binary search library.

KEY IDEA Halve the search space every step

Insight → because the array is sorted, comparing the middle element to the target immediately tells you which half the target can be in. Discard the useless half, repeat. Each iteration cuts the remaining candidates in half → O(log n) iterations total. You never need to look at more than ~log₂(n) elements.

RECIPE The lo/hi template

  • 0 · Set inclusive bounds. lo = 0, hi = nums.length - 1. Both endpoints are inside the current search window.
  • 1 · Loop while window is non-empty. Condition is lo <= hi (not <) so a single-element window is still checked.
  • 2 · Compute mid safely. mid = lo + Math.floor((hi - lo) / 2) instead of (lo + hi) / 2 — avoids integer overflow when lo + hi exceeds 32 bits.
  • 3 · Inspect and eliminate. If nums[mid] === target, return mid. If nums[mid] < target, everything up to and including mid is too small → move lo to mid + 1. Otherwise move hi to mid - 1.
  • 4 · Miss → return -1.If the loop exits without finding the target, it isn't in the array.
Classic confusion → should the loop be lo < hi or lo <= hi? With inclusive bounds (both lo and hi point at valid candidates), use <=. Switching to exclusive hi = nums.length and lo < hi is equally correct but mixes the two styles silently. Pick one template and stick to it.

COST Complexity & alternatives

Linear scan
O(n)
Check every element. Fine for small or unsorted input.
Binary search
O(log n)
O(log n) time; O(1) space (iterative).

Space note

The iterative version uses O(1) extra space — just two integer pointers. A recursive version uses O(log n) stack space. Always prefer iterative unless the problem requires recursion.

Pattern transfer → this exact template reappears in Search in Rotated Sorted Array (binary search with a twist on which half is sorted), Find Minimum in Rotated Array, Koko Eating Bananas (binary search on the answer space), and Median of Two Sorted Arrays. Master the inclusive-bounds template here and you unlock all of them.

RUN IT Halve the window until you find the target

step 0 / 4
STARTSearch begins. lo=0, hi=5. Amber cells are the active window.
1function search(nums: number[], target: number): number {
2▶  let lo = 0;
3▶  let hi = nums.length - 1;
4 
5  while (lo <= hi) {
6    const mid = lo + Math.floor((hi - lo) / 2); // avoid overflow
7    if (nums[mid] === target) return mid;
8    if (nums[mid] < target)  lo = mid + 1;       // target is right
9    else                      hi = mid - 1;       // target is left
10  }
11  return -1;   // not found
12}
nums =-1001325394125
State
0
lo
5
hi
—
mid
—
nums[mid]
active windowmid (current probe)exhausted / not foundfound
slowfast

TYPESCRIPT The solution, annotated

binarySearch.ts
function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoid overflow
    if (nums[mid] === target) return mid;
    if (nums[mid] < target)  lo = mid + 1;       // target is right
    else                      hi = mid - 1;       // target is left
  }
  return -1;   // not found
}

Reading it block by block

Lines 2–3 — initialise inclusive bounds. lo starts at index 0; hi starts at the last valid index nums.length - 1. Both pointers point at real elements, so the loop condition is <=.
Line 5 — loop while a window exists. lo <= hi ensures we still check the window even when it shrinks to a single element. If we used <we'd miss the final candidate.
Line 6 — overflow-safe midpoint. lo + Math.floor((hi - lo) / 2) is mathematically identical to Math.floor((lo + hi) / 2) but avoids overflow when both pointers are large. This matters in Java/C++; in JS numbers are 64-bit floats, but the idiom is still canonical.
Lines 7–9 — inspect and eliminate. Three branches: exact hit returns immediately; too-small means the target is to the right so lo = mid + 1 (not mid — we already know midisn't the answer); too-large means hi = mid - 1 for the same reason.
Line 11 — not found. The loop exits when lo > hi — the window collapsed with no match. Return -1.
Complexity → O(log n) time — each iteration eliminates at least half the remaining candidates. O(1) extra space — only two integer pointers, no auxiliary structure.

INTERVIEWFollow-ups they'll ask

  • "What if duplicates exist?" This exact template still finds an occurrence. To find the leftmost or rightmost index, bias mid and keep searching rather than returning on match — that pattern is Find First and Last Position (LC 34).
  • "What if the array is rotated?"At least one half is still sorted. Check which half and binary search within it — that's Search in Rotated Sorted Array (LC 33).
  • "Binary search on the answer?" Instead of searching an array, search a range of candidate answers and check feasibility with a helper. Classic examples: Koko Eating Bananas, Minimum Capacity to Ship Packages.
  • "Recursive version?" Equivalent, but uses O(log n) stack frames. The iterative approach is preferred in production.
  • "What's the brute force?" A linear scan is O(n). Binary search wins whenever the data is already sorted or we control the sort cost.

OPTIMAL Binary Search

binarySearch.ts
function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoid overflow
    if (nums[mid] === target) return mid;
    if (nums[mid] < target)  lo = mid + 1;       // target is right
    else                      hi = mid - 1;       // target is left
  }
  return -1;   // not found
}
Complexity → O(log n) time — each iteration eliminates at least half the remaining candidates. O(1) extra space — only two integer pointers, no auxiliary structure.

ALT 1 Brute force — linear scan

O(n) time · O(1) space

Ignore that the array is sorted and just walk it left to right, returning the first index whose value equals target— the baseline that works on any array, sorted or not.

approach-2.ts
function search(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}
Note → This touches every element in the worst case, so it's O(n) and throws away the one guarantee the problem hands you: the array is sorted. Halving the search range each step uses that order to reach O(log n).

MNEMONIC The one-liner

"lo and hi squeeze inward; mid is always overflow-safe; never exclude lo===hi."

TRIGGERS When you see ___ → reach for ___

sorted array, find targetlo/hi binary search template
"find first / last position"binary search + keep going on match
"minimize / maximize X such that feasible"binary search on the answer
rotated sorted arraybinary search — pick the sorted half

SKELETON The reusable shape

skeleton.ts
function search(nums: number[], target: number): number {
  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[mid] < target)  lo = mid + 1;
    else                      hi = mid - 1;
  }
  return -1;
}

FLASHCARDS Tap to flip

Why use lo <= hi (not lo < hi)?
Inclusive bounds: both lo and hi point at real candidates, so a window of size 1 (lo === hi) must still be checked.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
With nums = [-1, 0, 3, 5, 9, 12] and target = 9, what index does the algorithm return?
QUESTION 02
What is the time complexity of binary search?
QUESTION 03
Why is mid = lo + Math.floor((hi - lo) / 2) preferred over Math.floor((lo + hi) / 2)?
QUESTION 04
The loop condition is lo <= hi. What goes wrong if you write lo < hi instead (keeping the same inclusive bounds)?
QUESTION 05
After computing mid and finding nums[mid] < target, you set:
QUESTION 06
Binary search requires the input array to be:
QUESTION 07
You want to find the leftmost index of a target that may appear multiple times. What change do you make to the standard template?
QUESTION 08
#704 · Binary SearchThe canonical lo/hi/mid template: compare nums[mid] to the target and halve the search space each iteration until the target is found or the window collapses, in O(log n).Which algorithmic approach does this primarily use?
QUESTION 09
#704 · Binary SearchThe canonical lo/hi/mid template: compare nums[mid] to the target and halve the search space each iteration until the target is found or the window collapses, in O(log n).Which implementation correctly solves it?