Searching

Table of Contents

1. Finding Things Is the Most Common Job
2. Linear Search
3. Binary Search
4. Why It Is So Fast
5. Off-by-One Pitfalls
6. Lower Bound and Upper Bound
7. Binary Search on a Rotated Array
8. Binary Search on the Answer
9. Searching in Practice
10. Recipe: searching.ts for algolab
11. Try It Yourself

1. Finding Things Is the Most Common Job

Most programs spend their lives looking for something. Which user has this email? Is this word in the dictionary? Which release first broke the build? What is the smallest server size that can handle the load?

How you search depends on what you know about the data:

• Nothing: you must look at items one by one. That is linear search.
• It is sorted: you can throw away half of the data with each look. That is binary search.
• It is in a hash map: you jump straight to it (chapter 3). That is the fastest, but only works for exact matches.

This chapter covers the first two, and then shows a surprising use of binary search: finding an answer to a question when there is no array at all. It is one of the most useful tricks in interviews, and it is also famous for being easy to get slightly wrong. We will go slowly through the details.

2. Linear Search

Linear search checks every item from the start until it finds the target or runs out of items:

function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

const ids = [42, 7, 19, 3, 88];

console.log(linearSearch(ids, 19)); // 2
console.log(linearSearch(ids, 50)); // -1

Returning -1 for "not found" is a convention borrowed from Array.prototype.indexOf. It works because no real index is negative.

In the worst case the target is last, or missing, so we look at all n items: O(n). The best case is the first item: O(1).

JavaScript already has linear search built in. indexOf, includes, find, and findIndex all do exactly this loop for you. Use them when the array is small or unsorted. Linear search is not "bad": for 50 items it is faster than any clever alternative, because there is nothing to set up.

3. Binary Search

Think of a number from 1 to 100 and have a friend guess it. A smart friend says 50. You say "higher". They say 75. You say "lower". Each guess cuts the remaining range in half. After at most 7 guesses they have it. That is binary search.

The one requirement: the data must be sorted. Without order, "higher" and "lower" mean nothing.

Here is the algorithm on a sorted array. Keep two pointers, lo and hi, around the part that could still contain the target. Look at the middle. If it is too small, the target must be to the right. If it is too big, it must be to the left:

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

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

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

const scores = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

console.log(binarySearch(scores, 23)); // 5
console.log(binarySearch(scores, 7));  // -1
console.log(binarySearch(scores, 2));  // 0
console.log(binarySearch(scores, 91)); // 9

Here is a trace of searching for 23. The "range" is lo to hi:

Three looks instead of six. On 10 items that is a small win. The next section shows why it becomes enormous on large data.

4. Why It Is So Fast

Each step halves the range. How many times can you halve n before you reach 1? About log₂ n times. This is the logarithm from the Big-O chapter in Math for Programmers: the number of halvings.

A billion items, and only 30 looks. Doubling the data adds just one more step.

Let us measure it. Save this as bench-search.ts in algolab (we will turn the functions into a proper module in the recipe, so for now they are copied in):

function linearSearch(items: number[], target: number): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

function binarySearch(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const big = Array.from({ length: 5_000_000 }, (_, i) => i * 2);
const worst = 9_999_998; // the last value in the array

let t = performance.now();
for (let i = 0; i < 100; i++) linearSearch(big, worst);
console.log("linear x100:", (performance.now() - t).toFixed(1), "ms");

t = performance.now();
for (let i = 0; i < 100; i++) binarySearch(big, worst);
console.log("binary x100:", (performance.now() - t).toFixed(3), "ms");

npx tsx bench-search.ts

On one laptop the output was:

linear x100: 188.0 ms
binary x100: 0.097 ms

Your numbers will differ, but the gap will be huge: here about two thousand times faster. One caveat: binary search needs sorted data. If your data arrives unsorted, you must sort it first (next chapter), which costs O(n log n). That pays off only if you search many times. One search on unsorted data? Just use linear search.

5. Off-by-One Pitfalls

Binary search is a classic: the idea is simple, but the details are easy to break. Jon Bentley, who wrote a famous book on programming, reported that when he asked professional programmers to write it, only a small share got it fully right. The bugs are almost always off-by-one errors. Here are the four places to check.

1. The loop condition. We wrote while (lo <= hi) because lo and hi are both included in the range. When lo === hi, one item is left and it still needs checking. If you wrote lo < hi you would skip that last item and miss a target sitting there. Try it: search for 2 in [2] and see.

2. Moving the pointers. After checking mid, we know it is not the target, so we move past it: lo = mid + 1 and hi = mid - 1. If you write lo = mid instead, then when lo and mid are the same, nothing changes and the loop runs forever.

3. Calculating the middle. We wrote lo + Math.floor((hi - lo) / 2) and not Math.floor((lo + hi) / 2). In JavaScript, numbers are safe up to about 9 quadrillion, so lo + hi will not overflow for any real array. But in languages with 32-bit integers (Java, C), lo + hi can overflow for arrays over a billion items. This exact bug sat in Java's standard library for years. The safe form costs nothing, so use it as a habit.

4. The initial hi. In this version hi = length - 1, the last valid index, because the range is inclusive. A common mistake is to mix up styles: start with hi = length (exclusive) but keep the lo <= hi loop and hi = mid - 1. Then sorted[hi] can be undefined and the logic breaks.

The fix for all four is the same: pick one style and stay consistent. There are two styles:

The inclusive style above is good for "find this exact value". The half-open style is better for the next section, where the answer might be "the position where it would go", including one past the end.

6. Lower Bound and Upper Bound

What if the array has duplicates?

const data = [1, 2, 2, 2, 3, 5];

binarySearch(data, 2) returns some index of a 2, but which one? That depends on where mid happens to land. Often you need something more precise:

• Lower bound: the index of the first item that is >= target.
• Upper bound: the index of the first item that is > target.

Both are always defined, even when the target is missing, because they return "where it would be inserted". That makes them far more useful than -1:

function lowerBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length; // half-open: hi can be one past the end

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;
  }

  return lo;
}

function upperBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] <= target) lo = mid + 1;
    else hi = mid;
  }

  return lo;
}

const data = [1, 2, 2, 2, 3, 5];

console.log(lowerBound(data, 2)); // 1  (first 2)
console.log(upperBound(data, 2)); // 4  (just after the last 2)
console.log(lowerBound(data, 4)); // 5  (4 would be inserted before 5)
console.log(lowerBound(data, 9)); // 6  (past the end)
console.log(lowerBound(data, 0)); // 0  (before everything)

The two functions differ by a single character: < versus <=. Read them as "keep moving right while the item is too small to be the answer". For lower bound, "too small" means < target. For upper bound it means <= target.

Three useful tricks follow immediately:

// How many times does target appear?
function countOf(sorted: number[], target: number): number {
  return upperBound(sorted, target) - lowerBound(sorted, target);
}

console.log(countOf(data, 2)); // 3
console.log(countOf(data, 4)); // 0

• Exists? lowerBound(a, x) < a.length && a[lowerBound(a, x)] === x.
• Insert position: lowerBound tells you where to splice a new item in to keep the array sorted.
• Range query: "how many orders were placed between two timestamps?" is lowerBound(end) - lowerBound(start) on a sorted list of timestamps. This is how a database range query over an index works, just with a tree instead of an array.

7. Binary Search on a Rotated Array

Interviewers love this one. A sorted array was rotated at some pivot, so [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]. Find a target in O(log n).

The array is no longer fully sorted, but a key fact helps: if you split it at any mid, at least one half is still sorted. Check which half is sorted, ask "is the target inside that sorted half?", and keep or discard that half:

function searchRotated(nums: number[], target: number): number {
  let lo = 0;
  let 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]) {
      // the left half [lo..mid] is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // the right half [mid..hi] is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }

  return -1;
}

const rotated = [4, 5, 6, 7, 0, 1, 2];

console.log(searchRotated(rotated, 0)); // 4
console.log(searchRotated(rotated, 3)); // -1
console.log(searchRotated(rotated, 4)); // 0
console.log(searchRotated(rotated, 2)); // 6

Note nums[lo] <= nums[mid] uses <=, not <. When lo === mid (a single item) the "left half" is just that one item, and it counts as sorted. This detail is exactly the kind of off-by-one that fails hidden tests. This version assumes no duplicate values; with duplicates the worst case degrades to O(n).

8. Binary Search on the Answer

Here is the idea that makes binary search a general tool. You do not need an array. You need a yes/no question that flips only once as you move through the possible answers:

answer:   1   2   3   4   5   6   7 ...
ok?:      no  no  no  yes yes yes yes ...

If "is x enough?" is no for small x and yes from some point on (a monotonic condition), you can binary search for that first "yes", without ever building a list. The "array" is just the range of candidate answers.

Here is a reusable helper. It finds the smallest x in [lo, hi] for which ok(x) is true, and assumes ok(hi) is true:

function binarySearchAnswer(
  lo: number,
  hi: number,
  ok: (x: number) => boolean,
): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid; // mid works, but a smaller one might too
    else lo = mid + 1;     // mid fails, so the answer is bigger
  }
  return lo;
}

Example 1: slowest eating speed. A monkey has piles of bananas and hours hours to finish them. Each hour it picks one pile and eats up to speed bananas from it (a pile smaller than speed still takes the whole hour). What is the smallest speed that finishes in time?

If speed k works, any faster speed works too, so the condition flips once. For a given speed, counting hours is easy: each pile takes Math.ceil(pile / speed) hours.

function minSpeed(piles: number[], hours: number): number {
  return binarySearchAnswer(1, Math.max(...piles), (speed) => {
    let total = 0;
    for (const p of piles) total += Math.ceil(p / speed);
    return total <= hours;
  });
}

console.log(minSpeed([3, 6, 7, 11], 8));      // 4
console.log(minSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minSpeed([30, 11, 23, 4, 20], 6)); // 23

Why is Math.max(...piles) the upper limit? At that speed, every pile takes exactly one hour, which is the fastest it could ever be. Each check costs O(n) and we do about log₂(max) checks, so the whole thing is O(n log max). A brute-force try of every speed would be O(n × max).

Example 2: integer square root. The largest integer x such that x * x <= n. Flip the question: find the first x where x * x > n, then step back by one:

function mySqrt(n: number): number {
  return binarySearchAnswer(0, n + 1, (x) => x * x > n) - 1;
}

console.log(mySqrt(0));  // 0
console.log(mySqrt(1));  // 1
console.log(mySqrt(8));  // 2
console.log(mySqrt(16)); // 4
console.log(mySqrt(17)); // 4

The same recipe solves "ship packages within D days", "split an array into k parts with the smallest largest sum", "minimum time to repair cars", and many more. The pattern to spot is: "find the minimum (or maximum) value such that some condition holds", and checking a single candidate is cheaper than finding the answer directly.

To search for the maximum value that works, flip it. Find the first value where the condition fails and subtract one, just like we did in mySqrt.

9. Searching in Practice

Where you meet these ideas at work:

git bisect is the best demonstration. With 1,000 commits between a good and a bad release, it needs about 10 test runs to name the culprit. Linear checking could take 1,000.

A few rules of thumb:

• Unsorted and searched once: linear search.
• Many searches on the same data: sort once (or keep it sorted), then binary search; or build a Map if you only need exact matches.
• Need "closest", "first at least", or "how many in a range": sorted array and a bound search. A hash map cannot do these.
• Floating-point answers: binary search works there too, but loop a fixed number of times (say 100) instead of testing lo < hi, because decimals never become exactly equal.

10. Recipe: searching.ts for algolab

Create src/searching.ts and collect the functions from this chapter:

export function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

// Inclusive range [lo, hi]. Returns any matching index, or -1.
export function binarySearch(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// Half-open range [lo, hi). Index of the first item >= target.
export function lowerBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Index of the first item > target.
export function upperBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

export function countOf(sorted: number[], target: number): number {
  return upperBound(sorted, target) - lowerBound(sorted, target);
}

export function searchRotated(nums: number[], target: number): number {
  let lo = 0;
  let 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]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

// Smallest x in [lo, hi] where ok(x) is true. Assumes ok(hi) is true
// and that ok flips from false to true only once.
export function binarySearchAnswer(
  lo: number,
  hi: number,
  ok: (x: number) => boolean,
): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function minSpeed(piles: number[], hours: number): number {
  return binarySearchAnswer(1, Math.max(...piles), (speed) => {
    let total = 0;
    for (const p of piles) total += Math.ceil(p / speed);
    return total <= hours;
  });
}

export function mySqrt(n: number): number {
  return binarySearchAnswer(0, n + 1, (x) => x * x > n) - 1;
}

Now the tests in src/searching.test.ts. Binary search deserves more tests than most code, and the edge cases matter: empty array, one item, first item, last item, missing on both ends:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  linearSearch,
  binarySearch,
  lowerBound,
  upperBound,
  countOf,
  searchRotated,
  minSpeed,
  mySqrt,
} from "./searching.ts";

test("linearSearch finds the first match or returns -1", () => {
  assert.equal(linearSearch([42, 7, 19, 3, 88], 19), 2);
  assert.equal(linearSearch([42, 7, 19, 3, 88], 50), -1);
  assert.equal(linearSearch([], 1), -1);
});

test("binarySearch handles the edge cases", () => {
  const a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
  assert.equal(binarySearch(a, 23), 5);
  assert.equal(binarySearch(a, 2), 0);   // first item
  assert.equal(binarySearch(a, 91), 9);  // last item
  assert.equal(binarySearch(a, 7), -1);  // missing, in the middle
  assert.equal(binarySearch(a, 1), -1);  // smaller than everything
  assert.equal(binarySearch(a, 100), -1); // bigger than everything
  assert.equal(binarySearch([], 5), -1);
  assert.equal(binarySearch([5], 5), 0);
});

test("binarySearch agrees with linearSearch on every value", () => {
  const a = Array.from({ length: 50 }, (_, i) => i * 3);
  for (let x = -2; x <= 150; x++) {
    assert.equal(binarySearch(a, x), linearSearch(a, x));
  }
});

test("lowerBound, upperBound and countOf with duplicates", () => {
  const d = [1, 2, 2, 2, 3, 5];
  assert.equal(lowerBound(d, 2), 1);
  assert.equal(upperBound(d, 2), 4);
  assert.equal(lowerBound(d, 4), 5);
  assert.equal(lowerBound(d, 9), 6);
  assert.equal(lowerBound(d, 0), 0);
  assert.equal(countOf(d, 2), 3);
  assert.equal(countOf(d, 4), 0);
});

test("searchRotated", () => {
  const r = [4, 5, 6, 7, 0, 1, 2];
  assert.equal(searchRotated(r, 0), 4);
  assert.equal(searchRotated(r, 3), -1);
  assert.equal(searchRotated(r, 4), 0);
  assert.equal(searchRotated(r, 2), 6);
  assert.equal(searchRotated([1], 1), 0);
});

test("binary search on the answer", () => {
  assert.equal(minSpeed([3, 6, 7, 11], 8), 4);
  assert.equal(minSpeed([30, 11, 23, 4, 20], 5), 30);
  assert.equal(minSpeed([30, 11, 23, 4, 20], 6), 23);
  assert.equal(mySqrt(0), 0);
  assert.equal(mySqrt(8), 2);
  assert.equal(mySqrt(16), 4);
  assert.equal(mySqrt(17), 4);
});

Add the export to src/index.ts:

export * from "./searching.ts";

Run the tests:

npx tsx --test

You should see every test pass. The test named "agrees with linearSearch on every value" is worth remembering: when you have a slow, obviously correct version and a fast, tricky one, compare them over many inputs. This is the cheapest way to catch off-by-one bugs.

11. Try It Yourself

1. Break it on purpose. In binarySearch, change lo <= hi to lo < hi. Which test fails first, and what is the smallest array that exposes the bug? Then change lo = mid + 1 to lo = mid and run a search for a missing value. What happens, and why?
2. Insert position. Write insertSorted(sorted, value) that returns a new array with value inserted in the right place, using lowerBound. Why can inserting into the middle of an array still cost O(n) even though finding the spot is O(log n)? (Hint: chapter 2.)
3. First bad version (interview). Versions 1..n are released, and from some version on, every version is bad. You have a function isBad(v). Find the first bad version with the fewest calls. Which helper from this chapter solves it in one line?
4. Search a sorted matrix (interview). A matrix has rows sorted left to right, and each row starts with a number bigger than the last number of the row above. Search for a target in O(log(rows × cols)) by treating it as one long array and converting an index i to [Math.floor(i / cols), i % cols].
5. Ship in D days (interview). Packages with weights must be shipped in order, and a ship carries at most capacity per day. Find the smallest capacity that ships everything within days days. Use binarySearchAnswer. What are good values for lo and hi? (Hint: the heaviest package, and the sum of all packages.)
6. Peak finder. An array goes strictly up and then strictly down, like [1, 3, 8, 12, 9, 4, 2]. Find the index of the peak in O(log n). Compare a[mid] with a[mid + 1] to decide which side to keep.

Searching gets you from "look at everything" to "look at almost nothing" as soon as your data has some order. But we have been assuming the data is already sorted, and in real life it rarely is. In the next chapter, Sorting, we build the classic sorting algorithms, find out why [10, 9, 1].sort() gives a surprising answer, and measure which ones you can actually afford.