JS-201 · Lesson 8 of 12 · 25 min

Searching algorithms

▶ Video coming soon A video version of this lesson is on the way.

Lucy's dashboard has a search box. When she types part of a volunteer's name, the list underneath shows the matches, and when she picks a time of day, the dashboard highlights the shift running at that moment. With 300 volunteers both features felt instant. With the 3,000 records the Food Hub expects by the end of 2027, and every key press running a search, Gareth wants to be sure they still will. The eighth session, on Thursday, September 30, is about searching.

Searching is the problem of finding an item, or the place where it would be, in a collection. The best method depends on two things: whether the data is sorted, and how many times you will search it.

Linear search checks the items one at a time from the start until it finds a match or reaches the end. It works on any array, sorted or not, and it is what includes, indexOf, find, findIndex and some do. Its worst case is O(n). findLast and findLastIndex do the same from the end, which is useful when the most recent records are at the end and are the most likely matches.

For a single search, or a small array, linear search is the right choice: it is simple and needs no preparation. It becomes a problem only when it runs many times on a large array. A search box that runs a linear search on 3,000 names for every key press does 3,000 comparisons per key press, which is still fast; the trouble starts when that search sits inside another loop.

JavaScript Example · Linear search
const names = ['Okafor', 'Nguyen', 'Haddad', 'Silva', 'Moreau', 'Larsen', 'Tanaka', 'Novak'];
let steps = 0;
function linearSearch(a, target) {
  for (let i = 0; i < a.length; i++) { steps++; if (a[i] === target) return i; }
  return -1;
}

for (const t of ['Okafor', 'Larsen', 'Ahmed']) {
  steps = 0;
  console.log(t, '-> index', linearSearch(names, t), 'after', steps, 'steps');
}
console.log(names.findLast((n) => n.startsWith('N')));
Output
Okafor -> index 0 after 1 steps
Larsen -> index 5 after 6 steps
Ahmed -> index -1 after 8 steps
Novak

What this code does

linearSearch compares the target with each name in turn and returns its index, or -1 if it reaches the end without a match. A missing name costs a comparison with every element, which is the worst case. findLast searches from the end and returns the last name beginning with N.

If the array is sorted, there is a much faster method. Look at the middle element. If it is the target, stop. If the target is smaller, it can only be in the left half; if larger, only in the right half. Either way, one comparison throws away half of the remaining elements. Repeat on the half that is left. This is binary search, and because the range halves at every step, it needs at most about log₂ n + 1 comparisons.

A sorted row of fifteen numbers from 3 to 162, searched for 101. Step 1 marks low at 3, high at 162 and middle at 82; 101 is larger, so the left half is grayed out. Step 2 marks the middle of the right half at 120; 101 is smaller, so the range shrinks to 90, 95 and 101. Step 3 marks the middle at 95, and step 4 finds 101.
Binary search halves the range at each step: four steps find 101 among fifteen sorted numbers.

The numbers are striking. A sorted array of 1,000 items needs at most 10 comparisons, and one of 1,000,000 needs at most 20. Doubling the data adds only one comparison. That is O(log n), and it is why sorted data is so valuable.

JavaScript Example · Binary search
let steps = 0;
function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1;             // the target, if present, is in a[lo..hi]
  while (lo <= hi) {
    steps++;
    const mid = (lo + hi) >>> 1;
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;       // the target is to the right
    else hi = mid - 1;                       // the target is to the left
  }
  return -1;
}

const orders = [3, 9, 10, 21, 27, 38, 43, 82, 90, 95, 101, 120, 133, 150, 162];
steps = 0; console.log('101 at', binarySearch(orders, 101), 'in', steps, 'steps');
steps = 0; console.log('3 at', binarySearch(orders, 3), 'in', steps, 'steps');
steps = 0; console.log('100 at', binarySearch(orders, 100), 'in', steps, 'steps');

const million = Array.from({ length: 1000000 }, (_, i) => i * 2);
steps = 0; binarySearch(million, 1999998);
console.log('a million items, worst case:', steps, 'steps');
Output
101 at 10 in 4 steps
3 at 0 in 4 steps
100 at -1 in 4 steps
a million items, worst case: 20 steps

What this code does

binarySearch keeps lo and hi as the ends of the range where the target could still be. Each step compares the middle element and moves lo or hi past it, so the range halves. Finding 101 takes four steps, a missing number is reported as -1 once the range is empty, and even a million items need only twenty steps.

Getting binary search right

Binary search is famously easy to get almost right. Its correctness rests on an invariant, a statement that is true before every pass of the loop: if the target is in the array, it is somewhere in a[lo] to a[hi]. Each branch must keep that statement true and must make the range smaller. Moving lo to mid instead of mid + 1, for example, can leave the range the same size for ever, and the loop never ends.

The midpoint itself has a famous bug. In languages with fixed-size integers, (lo + hi) ÷ 2 can overflow when lo and hi are both large, a bug that sat in Java's standard library for nearly a decade. JavaScript numbers do not overflow at these sizes, but writing the midpoint as (lo + hi) >>> 1, an unsigned shift that halves and rounds down, is a common and safe habit. The best protection is testing: an empty array, one element, the first and last elements, a missing value smaller than everything, a missing value larger than everything, and duplicates.

Finding where a value belongs

Often the question is not whether a value is present but where it belongs. The lower bound of a target in a sorted array is the first index whose value is greater than or equal to the target. If the target is present, that is the index of its first copy; if not, it is the place to insert it to keep the array sorted. The loop is a slight variation of binary search that never stops early.

JavaScript Example · Lower bound and counting in a range
// First index whose value is >= target (a.length if there is none). a must be sorted.
function lowerBound(a, target) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const starts = [480, 540, 540, 600, 660, 780, 840];   // shift start times, minutes after midnight
console.log(lowerBound(starts, 540), lowerBound(starts, 541), lowerBound(starts, 0), lowerBound(starts, 900));

// Keep a sorted list sorted when a new shift is added.
const i = lowerBound(starts, 720);
starts.splice(i, 0, 720);
console.log(starts);

// How many shifts start between 9:00 and 12:00 inclusive?
const count = lowerBound(starts, 12 * 60 + 1) - lowerBound(starts, 9 * 60);
console.log('shifts starting 9:00 to 12:00:', count);
Output
1 3 0 7
[ 480, 540, 540, 600, 660, 720, 780, 840 ]
shifts starting 9:00 to 12:00: 5

What this code does

lowerBound narrows the range until lo is the first position whose value is at least the target, so 540 gives the first of its two copies and 541 gives the position after them. A target larger than everything gives the array's length. Two lower bounds subtracted count the values in a range, here the shifts starting from 9:00 up to and including 12:00, in O(log n) time.

Inserting with splice still moves the elements after the insertion point, so adding to a sorted array is O(n) even though finding the place is O(log n). For a few thousand items that is fine. For a structure that stays sorted under many insertions, a balanced search tree, from the next lesson, keeps both parts O(log n).

Searching intervals

Lucy's second feature asks which shift is running at a given moment. If the shifts in a day are sorted by start time and do not overlap, the running shift is the last one that starts at or before that moment. That is one less than the lower bound of the first start after the moment, followed by a check that the shift has not already ended.

JavaScript Example · Which shift is running?
// First index whose value is >= target (a.length if there is none). a must be sorted.
function lowerBound(a, target) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const shifts = [
  { area: 'Grocery', start: 480, end: 600 }, { area: 'Kitchen', start: 600, end: 720 },
  { area: 'Counter', start: 720, end: 840 }, { area: 'Garden', start: 900, end: 1020 },
];
const startTimes = shifts.map((s) => s.start);

function runningAt(minute) {
  const i = lowerBound(startTimes, minute + 1) - 1;     // last shift starting at or before minute
  if (i < 0 || minute >= shifts[i].end) return 'no shift';
  return shifts[i].area;
}
const hhmm = (m) => String(Math.floor(m / 60)).padStart(2, '0') + ':' + String(m % 60).padStart(2, '0');
for (const m of [470, 480, 615, 839, 860, 930]) console.log(hhmm(m), runningAt(m));
Output
07:50 no shift
08:00 Grocery
10:15 Kitchen
13:59 Counter
14:20 no shift
15:30 Garden

What this code does

runningAt uses lowerBound on the start times to find the last shift that has started by the given minute. It then checks whether that shift has already ended, which covers the gap between 14:00 and 15:00. Each lookup is O(log n), so the dashboard could check every minute of the day without slowing down.

Searching text

The name search box is a different kind of search: Lucy types part of a name, and every name containing it should match. includes on each name checks every position in the name, so the whole search is O(total length of all names). For 3,000 names that is around 30,000 character checks per key press, comfortably fast. Faster text search, for millions of documents, uses structures such as an inverted index, which search engines and databases provide.

The harder part is matching what people mean. Lucy types "emile" and expects to find Émile; she types "ana " with a trailing space. Normalizing both the names and the query first, by trimming spaces, converting to lower case and removing accents, makes the search match the way people think. normalize('NFD') splits an accented letter into its base letter followed by a separate accent mark, and a regular expression can then remove the accent marks.

JavaScript Example · Accent-insensitive name search
function fold(s) {
  return s.trim().toLowerCase().normalize('NFD').replace(/[\u0300-\u036f]/g, '');
}
const people = ['Émile Roy', 'Ana Silva', 'Anaïs Côté', 'Ben Okafor', 'Zoë Novak'];
const folded = people.map(fold);                       // fold once, not on every key press

function search(query) {
  const q = fold(query);
  return people.filter((p, i) => folded[i].includes(q));
}
console.log(search('emile'));
console.log(search('ana '));
console.log(search('COTE'));
console.log(search('zoe'));
Output
[ "Émile Roy" ]
[ "Ana Silva", "Anaïs Côté" ]
[ "Anaïs Côté" ]
[ "Zoë Novak" ]

What this code does

fold trims the text, lowers its case and splits each accented letter into a base letter plus an accent mark, which the regular expression then removes. The names are folded once in advance, so each key press only folds the short query. The searches now find Émile from emile and Côté from COTE.

Two pointers on sorted data

Sorted data allows another technique: two indexes moving toward each other, or alongside each other, so that a problem that looks like it needs nested loops is solved in one pass. To find two hampers whose weights add up to a target in a sorted list, start one pointer at the lightest and one at the heaviest. If their sum is too small, move the left pointer right to a heavier hamper; if too large, move the right pointer left. Each step rules out one hamper for good, so the search is O(n).

JavaScript Example · Two pointers on a sorted list
function pairWithSum(sorted, target) {
  let i = 0, j = sorted.length - 1, steps = 0;
  while (i < j) {
    steps++;
    const sum = sorted[i] + sorted[j];
    if (sum === target) return { pair: [sorted[i], sorted[j]], steps };
    if (sum < target) i++;
    else j--;
  }
  return { pair: null, steps };
}

const weights = [5800, 7400, 8200, 9100, 10600, 11800, 12500];   // hamper weights, sorted
console.log(pairWithSum(weights, 17300));
console.log(pairWithSum(weights, 30000));
Output
{ pair: [ 8200, 9100 ], steps: 6 }
{ pair: null, steps: 6 }

What this code does

pairWithSum starts with the lightest and heaviest hampers and moves one pointer inwards at each step depending on whether the sum is too small or too large. Every step permanently rules out one hamper, so the loop runs at most n minus 1 times. It needs the list to be sorted, unlike the Map method from Lesson 5.

Binary search on the answer

Binary search also works on questions whose answer is a number, as long as the question has a yes-or-no test that switches from no to yes at one point. Rosa plans to send the lunch counter's surplus meals to three pick-up points in a fixed order of trays, and wants the smallest cart capacity that lets the volunteer do it in at most a given number of trips, without reordering the trays. Any capacity above the answer works and any below fails, so the answer can be found by binary search between the heaviest single tray and the total weight.

JavaScript Example · Binary search on the answer
// Trips needed if each trip carries consecutive trays up to capacity.
function tripsNeeded(trays, capacity) {
  let trips = 1, load = 0;
  for (const t of trays) {
    if (load + t > capacity) { trips++; load = 0; }
    load += t;
  }
  return trips;
}
function smallestCapacity(trays, maxTrips) {
  let lo = Math.max(...trays), hi = trays.reduce((a, b) => a + b, 0), tests = 0;
  while (lo < hi) {
    tests++;
    const mid = Math.floor((lo + hi) / 2);
    if (tripsNeeded(trays, mid) <= maxTrips) hi = mid;   // mid works: try smaller
    else lo = mid + 1;                                   // mid fails: need bigger
  }
  return { capacity: lo, tests };
}

const trays = [12, 8, 15, 6, 9, 14, 7, 11];   // tray weights, in loading order
for (const k of [1, 2, 3, 4]) console.log(k, 'trips:', smallestCapacity(trays, k));
Output
1 trips: { capacity: 82, tests: 6 }
2 trips: { capacity: 41, tests: 6 }
3 trips: { capacity: 32, tests: 7 }
4 trips: { capacity: 23, tests: 6 }

What this code does

tripsNeeded loads trays in order and starts a new trip whenever the next tray would exceed the capacity. smallestCapacity searches between the heaviest tray and the total, keeping any capacity that works and moving above any that fails, so it homes in on the smallest one that works. Each answer needs only a handful of tests instead of trying every capacity.

Choosing a search strategy

Choosing how to search.
SituationBest approachCost
One search in unsorted dataLinear searchO(n)
Many exact-match searchesBuild a Map or Set onceO(n) once, then O(1) average
Many searches for ranges, nearest values or positionsSort once, then binary searchO(n log n) once, then O(log n)
Text containing a phrase, small dataNormalize once, then includesO(total text length)
Pairs or matches in sorted dataTwo pointersO(n)
Smallest value that passes a yes-or-no testBinary search on the answerO(log range) tests

For Lucy's dashboard, Mira's plan is a Map from id to volunteer for exact lookups, a folded copy of the names for the search box, and the day's shifts sorted by start time with lowerBound for the clock feature. Each structure costs O(n) or O(n log n) once when the data loads and makes every later search cheap.

Try it yourself

Where does the new booking go?

Complete insertSorted(a, value) so that it inserts value into the sorted array a at the position that keeps it sorted, after any equal values, and returns the index used.

Find the position with a binary search for the first value greater than value, then use splice.

function insertSorted(a, value) {
  a.push(value);
  return a.length - 1;
}

const times = [480, 540, 540, 600, 720];
console.log(insertSorted(times, 540), insertSorted(times, 300), insertSorted(times, 800));
console.log(times.join(' '));

Try it yourself

Hampers in a weight range

The weights array is sorted. Complete countBetween(weights, low, high) so that it returns how many weights are at least low and at most high, using the lowerBound function provided twice.

The function should be O(log n), not a loop over the whole array.

// First index whose value is >= target (a.length if there is none). a must be sorted.
function lowerBound(a, target) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function countBetween(weights, low, high) {
  return weights.filter((w) => w > low && w < high).length;
}

const weights = [5800, 7400, 8200, 8200, 9100, 10600, 11800, 12500];
console.log(countBetween(weights, 8200, 10600), countBetween(weights, 0, 6000), countBetween(weights, 13000, 20000));

Common mistakes

  • MistakeRunning binary search on unsorted data.

    InsteadBinary search only works on sorted data; on anything else it returns wrong answers without any error.

  • MistakeSetting lo = mid or hi = mid in the classic loop.

    InsteadThe range may stop shrinking and the loop may never end. Move past mid.

  • MistakeSorting the array before every search.

    InsteadSorting is O(n log n), worse than one linear search. Sort once and search many times.

  • MistakeFolding the whole list of names on every key press.

    InsteadFold the names once when they load and only fold the query each time.

  • MistakeAssuming splice into a sorted array is O(log n).

    InsteadFinding the place is O(log n), but splice moves the elements after it, which is O(n).

Summary and key terms

  • Linear search checks items one at a time, works on any array and costs O(n); includes, indexOf, find and findLast all do it.
  • Binary search needs sorted data and halves the range at each comparison, so it costs O(log n), about 20 steps for a million items.
  • Its correctness rests on the invariant that the target lies between lo and hi and on shrinking that range every pass; test empty arrays, ends, duplicates and missing values.
  • The lower bound is the first index whose value is at least the target, giving the insertion point and, with two calls, the count of values in a range.
  • Sorted intervals can be searched for the one containing a moment.
  • Text search should normalize case, spaces and accents, folding the data once.
  • Two pointers on sorted data solve pair problems in O(n).
  • Binary search on the answer finds the smallest value passing a yes-or-no test.
  • Choose by whether the data is sorted and how often it is searched.
linear search
Checking items one at a time until a match is found or the end is reached.
binary search
Searching sorted data by comparing with the middle item and discarding half of the range each time.
invariant
A statement that stays true at a chosen point every time a loop runs, used to reason about correctness.
lower bound
The first position in a sorted array whose value is greater than or equal to a target.
insertion point
The position at which a value can be inserted into a sorted array while keeping it sorted.
off-by-one error
A mistake in which a loop or index goes one step too far or stops one step short.
normalization
Converting text to a standard form, such as lower case without accents, before comparing it.
two pointers
A technique that moves two indexes through sorted data to solve a problem in one pass.
binary search on the answer
Finding the smallest or largest value that passes a yes-or-no test by halving the range of possible values.
inverted index
A map from each word to the documents containing it, used by search engines.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. At most how many comparisons does binary search need for 1,000,000 sorted items?

    Show answer

    About 20, because 2²⁰ is just over a million.

  2. What does lowerBound return for a target larger than every element?

    Show answer

    The array's length, which is the position to append it.

  3. How do you count the values from 10 to 20 in a sorted array of whole numbers?

    Show answer

    lowerBound(a, 21) − lowerBound(a, 10).

  4. Why fold the names once rather than in the filter?

    Show answer

    Folding every name on every key press repeats the same O(n) work.

  5. What property must a question have for binary search on the answer to work?

    Show answer

    Its yes-or-no test must switch from no to yes at a single point as the value increases.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz