Search Algorithms lessons

Linear search

Linear search checks each item in turn, from the first to the last. It stops when it finds the target or runs out of items.

Linear search scanning an unsorted list of ten numbers, with each index and a check counter.

It works on any list, sorted or not. That makes it the simplest search, but also the slowest on a big list.

Linear search in code

The loop moves an index i from 0 to the end of the list. If the item at i matches the target, the function returns i.

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

console.log(linearSearch([42, 7, 19, 88, 3], 19)); // 2
console.log(linearSearch([42, 7, 19, 88, 3], 50)); // -1

If the loop ends without a match, it returns -1 to mean not found. The best case is one check, when the target comes first.

The worst case is when the target is last or missing. Then a list of n items takes n checks.

Practice: Count the checks

Type how many checks linear search makes to find a target in a random list, or to give up.

Binary search

Binary search only works on a sorted list. It starts by checking the middle item.

Binary search on 16 sorted numbers: low, mid and high, the middle checked, half the range dropped each step.

If the target is bigger, the whole left half can go. If it is smaller, the right half goes, and the search repeats on what is left.

Binary search in code

Two indexes, low and high, mark the part of the list still in play. Each pass of the loop checks the middle index, mid.

function binarySearch(list, target) {
  let low = 0;
  let high = list.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

console.log(binarySearch([3, 9, 14, 20, 27, 31, 40], 27)); // 4

Moving low or high past mid throws away half the range. When low passes high, nothing is left, so the target is missing.

Practice: Find the middle

Tap the item binary search checks next, given the range still in play.

Why the list must be sorted

Binary search assumes that everything left of the middle is smaller. On an unsorted list that is not true, so it can throw away the half that holds the target.

Binary search on the same seven numbers, unsorted and sorted: the unsorted search throws the target away.

Sorting fixes this, but sorting takes work too. It pays off when you search the same list many times.

Practice: Sorted or not?

Sort lists and real collections into the ones binary search can handle and the ones that need linear search.

Counting steps

We compare searches by counting their checks in the worst case. For linear search on n items, that is n checks.

Binary search halving 32 items: 32 \to 16 \to 8 \to 4 \to 2 \to 1

Binary search halves the range with each check. It takes 5 halvings to get from 32 items down to 1, because 2^5 = 32.

That count is written \log_2 32 = 5. So binary search needs about \log_2 n checks.

Practice: Count the halvings

Type log base 2 of a list size, or the list size from a number of halvings.

Big O notation

Big O notation describes how the number of steps grows as the input size n grows. It keeps only the part that grows fastest.

1. O(1) (constant: the same steps for any n)
2. O(\log n) (logarithmic: halve the data each step)
3. O(n) (linear: check every item once)
4. O(n^2) (quadratic: compare every pair of items)

Binary search is O(\log n) and linear search is O(n). A hash table lookup is O(1), as you will see soon.

Watching the steps grow

Small lists hide the difference. As n grows, the step counts pull apart fast.

Plot of steps against n for O(1), O(log n), O(n) and O(n squared), with n on a slider and the step counts read out.

At a million items, \log_2 n is only about 20. An O(n^2) algorithm would need a million million steps.

Practice: Match the Big O

Drag each Big O onto the task that grows that way.

Hash tables

A hash table stores items in numbered slots called buckets. A hash function turns each key into a bucket number.

Names hashed into 8 buckets by adding letter values, then looked up by hashing again.

To find a key, you hash it again and go straight to its bucket. There is no scanning, so a lookup is O(1) on average.

Collisions

Two keys can land in the same bucket. This is a collision, and the bucket keeps a short list of both.

A lookup then checks that short list, which is still quick. A good hash function spreads keys out, so the lists stay short.

In JavaScript, a Map is a ready-made hash table.

const phoneBook = new Map();
phoneBook.set("Amy", "555-0142");
phoneBook.set("Ben", "555-0199");

console.log(phoneBook.get("Amy")); // 555-0142
console.log(phoneBook.has("Cal")); // false

Practice: Find the bucket

Add the letter values of a name and type the remainder to find its bucket.

Trees and graphs

Not all data sits in a list. A tree branches out from one top node, the root, and each node links down to its children.

A tree beside a graph: one path from the root to any node, and a loop in the graph.

A graph is a set of nodes joined by edges in any pattern, loops included. Road maps and social networks are graphs.

Depth-first search

Depth-first search (DFS) follows one branch as deep as it goes, then backs up. It keeps the nodes still to visit on a stack.

DFS walking a seven-node tree, with the stack and the visit order shown.

A stack is last in, first out, like a pile of plates. The node added most recently is visited next.

Breadth-first search

Breadth-first search (BFS) visits every node on one level before going deeper. It keeps the waiting nodes in a queue.

BFS walking the same tree, with the queue and the visit order shown.

A queue is first in, first out, like a line at a shop. Because BFS goes level by level, it finds the nearest match first.

Stack or queue in code

Both searches use the same loop. The only difference is which end of the list the next node comes from.

const tree = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F", "G"],
  D: [], E: [], F: [], G: [],
};

function dfs(start) {
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const node = stack.pop(); // newest
    order.push(node);
    // right child first, so the left one is on top
    for (const child of [...tree[node]].reverse()) {
      stack.push(child);
    }
  }
  return order;
}

function bfs(start) {
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift(); // oldest
    order.push(node);
    for (const child of tree[node]) {
      queue.push(child);
    }
  }
  return order;
}

console.log(dfs("A").join(" ")); // A B D E C F G
console.log(bfs("A").join(" ")); // A B C D E F G

pop takes the newest node, which makes a stack. shift takes the oldest, which makes a queue.

A graph can loop back on itself, so there you also keep a set of visited nodes. Then no node is visited twice.

Practice: Order the visits

Place the nodes of a random tree in the order DFS or BFS visits them.

Choosing the right search

The best search depends on the data and on the question. A few yes or no checks point to the right one.

Scenarios walked through four questions, each landing on the search that fits.

Hash tables win for lookups by key. Binary search needs sorted data, and linear search works on anything.

Practice: Pick the search

Pick the best search for each real situation.