Linear and binary search

The problem: find order 734,512

A customer calls about order 734,512. The support tool has the day's export: a million orders in an array, one object per order. The orders were written as they were created, and order ids only ever go up, so the array is already sorted by id. How does the tool find the order?

The simplest way is to look at every order in turn until the id matches. That is linear search. Here it is, counting how many orders it looks at:

export const orders = Array.from({ length: 1_000_000 }, (_, i) => ({
  id: 100_000 + i * 3,
  totalKobo: 50_000 + ((i * 7919) % 900_000),
  placedAt: new Date(Date.UTC(2026, 8, 1) + i * 2_000).toISOString(),
}));

import { orders } from "./orders.js";

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

console.log("orders:", orders.length, "first id:", orders[0].id, "last id:", orders.at(-1).id);
for (const id of [100_000, 1_600_000, 734_512, 2_500_000, 734_513]) {
  const { index, looked } = linearSearch(orders, id);
  console.log(`id ${id}: index ${index}, looked at ${looked} orders`);
}

orders: 1000000 first id: 100000 last id: 3099997
id 100000: index 0, looked at 1 orders
id 1600000: index 500000, looked at 500001 orders
id 734512: index 211504, looked at 211505 orders
id 2500000: index 800000, looked at 800001 orders
id 734513: index -1, looked at 1000000 orders

Ids go up by 3 in this export (other ids belong to other shops), so 734,513 does not exist. Linear search is quick when the order is near the front, and it looks at all million orders when the order is at the end or missing, which is exactly when a customer is most upset. It is O(n): on average about n/2 looks for a present id, and always n for a missing one.

But this search ignores the most useful fact about the data: it is sorted. Binary search uses that fact to find any order, or prove it is missing, in about 20 looks. This lesson builds both, shows the bugs that make binary search famous for being hard to get right, and then generalises it into lower and upper bounds, which answer range questions such as "all orders placed on the 3rd".

Linear search, done properly

Linear search is not a beginner's mistake. It is the right tool when:

• the data is not sorted by what you search for (searching orders by customer name when they are sorted by id),
• the array is small (a few dozen items: the loop is faster than anything cleverer),
• you search once: sorting first costs O(n log n), more than the O(n) scan,
• the condition is not an equality: "the first order over ₦100,000", "the last failed payment".

JavaScript's arrays have linear search built in. All of these are O(n), and all stop at the first match:

const payments = [
  { ref: "PAY-1", status: "paid", kobo: 1_250_000 },
  { ref: "PAY-2", status: "failed", kobo: 480_000 },
  { ref: "PAY-3", status: "paid", kobo: 12_500_000 },
  { ref: "PAY-4", status: "failed", kobo: 90_000 },
];

console.log(payments.find((p) => p.kobo > 10_000_000)?.ref);
console.log(payments.findIndex((p) => p.status === "failed"));
console.log(payments.findLast((p) => p.status === "failed")?.ref);
console.log(payments.some((p) => p.kobo < 0));
console.log(payments.find((p) => p.ref === "PAY-9"));

const scores = [3, NaN, 7];
console.log(scores.indexOf(NaN), scores.includes(NaN));

PAY-3
1
PAY-4
false
undefined
-1 true

• find returns the item (or undefined); findIndex returns its index (or −1). findLast and findLastIndex search from the end, which is what you want for "most recent".
• some answers "is there any?" and stops at the first yes.
• indexOf and includes compare with a value instead of a function. They differ on NaN: indexOf uses ===, and NaN === NaN is false, so it never finds NaN; includes uses a comparison that treats NaN as equal to itself.
• Returning −1 or undefined for "not found" is a convention the caller must check. Forgetting to check is the most common linear-search bug: payments[-1] is undefined, and the error appears far from its cause.

Binary search

You already know binary search from the guessing game: "a number from 1 to 100", "50?", "lower", "25?", "higher"… Each answer throws away half of the remaining numbers, so 7 guesses always suffice, because 2⁷ = 128 ≥ 100.

On a sorted array: look at the middle item. If it is the one, done. If it is smaller than the target, the target can only be to the right, so throw away the left half; if it is larger, throw away the right half. Repeat on what remains. After k steps at most n / 2^k items remain, so after about log₂ n steps there is nothing left: O(log n). For a million orders, log₂ 1,000,000 ≈ 20.

The iterative version

export function binarySearch(items, id, stats = { looked: 0 }) {
  let lo = 0;
  let hi = items.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    stats.looked++;
    const current = items[mid].id;
    if (current === id) return mid;
    if (current < id) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

The key to getting it right is the loop invariant: a statement that is true before every iteration. Here it is: if the id is in the array at all, it is at an index between lo and hi, inclusive.

• At the start, lo = 0 and hi = length − 1 cover the whole array, so it is true.
• If items[mid].id is smaller than the target, then so is everything at or before mid (the array is sorted), so the target can only be at mid + 1 or later: lo = mid + 1 keeps the invariant. The hi = mid − 1 case is the mirror.
• The range lo..hi shrinks by at least one every time (mid itself is excluded), so the loop ends. When lo > hi the range is empty, and by the invariant the id is not in the array.

Every line of the function follows from that one sentence. When you write a binary search, write the invariant first.

import { orders } from "./orders.js";
import { binarySearch } from "./binary.js";

for (const id of [100_000, 1_600_000, 734_512, 2_500_000, 734_513, 99, 9_999_999]) {
  const stats = { looked: 0 };
  const index = binarySearch(orders, id, stats);
  console.log(`id ${id}: index ${index}, looked at ${stats.looked} orders`);
}
console.log("log2 of 1,000,000 =", Math.log2(1_000_000).toFixed(2));
console.log("empty array:", binarySearch([], 5));

id 100000: index 0, looked at 19 orders
id 1600000: index 500000, looked at 19 orders
id 734512: index 211504, looked at 20 orders
id 2500000: index 800000, looked at 20 orders
id 734513: index -1, looked at 20 orders
id 99: index -1, looked at 19 orders
id 9999999: index -1, looked at 20 orders
log2 of 1,000,000 = 19.93
empty array: -1

Never more than 20 looks, whether the order is first, last, in the middle, or missing, against up to a million for linear search. Double the orders and binary search needs one more look.

To see the range shrink, here is a trace on a small array of order ids:

const ids = [1004, 1011, 1015, 1020, 1032, 1047, 1051, 1066, 1070, 1089];

function traceSearch(items, target) {
  let lo = 0;
  let hi = items.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const verdict = items[mid] === target ? "found" : items[mid] < target ? "go right" : "go left";
    console.log(`  lo=${lo} hi=${hi} mid=${mid} items[mid]=${items[mid]} -> ${verdict}`);
    if (items[mid] === target) return mid;
    if (items[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  console.log(`  lo=${lo} hi=${hi}: empty range`);
  return -1;
}

console.log("search 1066:", traceSearch(ids, 1066));
console.log("search 1016:", traceSearch(ids, 1016));

  lo=0 hi=9 mid=4 items[mid]=1032 -> go right
  lo=5 hi=9 mid=7 items[mid]=1066 -> found
search 1066: 7
  lo=0 hi=9 mid=4 items[mid]=1032 -> go left
  lo=0 hi=3 mid=1 items[mid]=1011 -> go right
  lo=2 hi=3 mid=2 items[mid]=1015 -> go right
  lo=3 hi=3 mid=3 items[mid]=1020 -> go left
  lo=3 hi=2: empty range
search 1016: -1

When 1016 is not found, the search stops with lo = 3, which is exactly where 1016 would have to be inserted to keep the array sorted. Remember that; it becomes lower bound.

The recursive version

Binary search is a natural fit for recursion (from Recursion): searching the whole array means searching one half of it, which is the same problem, smaller. The base case is the empty range.

import { orders } from "./orders.js";

function binarySearchRecursive(items, id, lo = 0, hi = items.length - 1, depth = 1) {
  if (lo > hi) return { index: -1, depth };
  const mid = Math.floor((lo + hi) / 2);
  if (items[mid].id === id) return { index: mid, depth };
  if (items[mid].id < id) return binarySearchRecursive(items, id, mid + 1, hi, depth + 1);
  return binarySearchRecursive(items, id, lo, mid - 1, depth + 1);
}

console.log(binarySearchRecursive(orders, 734_512));
console.log(binarySearchRecursive(orders, 734_513));

{ index: 211504, depth: 20 }
{ index: -1, depth: 21 }

It does the same comparisons and is O(log n) in time. It also uses O(log n) stack frames, one per halving, which is harmless (21 frames for a million items, a few dozen for any array that fits in memory), unlike the O(n) recursion that crashed on deep trees. JavaScript engines do not remove those frames even though each call is the last thing its caller does, so the iterative loop is the usual choice in production code; the recursive one is often easier to reason about.

The classic bugs

A famous study found that most professional programmers, given time to write a binary search, produced one with a bug; a bug in the binary search of Java's standard library went unnoticed for nine years. The bugs are always at the edges. Here they are, each with its symptom.

Bug 1: while (lo < hi) with an inclusive range

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

const ids = [1004, 1011, 1015, 1020];
console.log(ids.map((id) => buggy(ids, id)).join(" "));
console.log(buggy([1004], 1004));

-1 1 2 -1
-1

With lo and hi both inclusive, a range with one item has lo === hi, and lo < hi refuses to look at it. Some items are "missing", and a one-item array never finds anything. The condition must match the meaning of hi: inclusive hi needs lo <= hi.

Bug 2: lo = mid instead of lo = mid + 1

function buggy(items, target) {
  let lo = 0;
  let hi = items.length - 1;
  let steps = 0;
  while (lo <= hi) {
    if (++steps > 50) return `gave up after 50 steps, stuck at lo=${lo} hi=${hi}`;
    const mid = Math.floor((lo + hi) / 2);
    if (items[mid] === target) return mid;
    if (items[mid] < target) lo = mid;
    else hi = mid - 1;
  }
  return -1;
}

const ids = [1004, 1011, 1015, 1020];
console.log(buggy(ids, 1011));
console.log(buggy(ids, 1030));

1
gave up after 50 steps, stuck at lo=2 hi=3

When lo and hi are neighbours, mid rounds down to lo, so lo = mid changes nothing and the loop never ends. Without the step guard, the support tool would hang, and a server would burn a CPU core per request. It only happens for some targets, so a quick test can miss it. The rule: every branch must shrink the range, which is why mid itself is always excluded (mid + 1, mid − 1).

Bug 3: a middle that is not a whole number

const ids = [1004, 1011, 1015, 1020];
const lo = 0;
const hi = 3;

console.log((lo + hi) / 2, ids[(lo + hi) / 2]);
console.log(Math.floor((lo + hi) / 2), ids[Math.floor((lo + hi) / 2)]);
console.log((3_000_000_000 + 3_000_000_002) >> 1, Math.floor((3_000_000_000 + 3_000_000_002) / 2));

1.5 undefined
1 1011
852516353 3000000001

ids[1.5] is undefined, and every comparison with undefined is false, so the search wanders off. Use Math.floor. The shift trick (lo + hi) >> 1 is popular because it is short, but bitwise operators convert to 32-bit integers, which breaks for indexes above about 2.1 billion: rare for arrays, common when you binary-search over numbers such as file offsets or timestamps. (Java's nine-year bug was the related overflow of lo + hi, which JavaScript's numbers avoid up to 2⁵³.)

Bug 4: data sorted differently from how you search

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

const prices = [9500, 12000, 150000, 800, 45000];
const wrong = [...prices].sort();
const right = [...prices].sort((a, b) => a - b);

console.log("default sort:", wrong.join(" "), "-> find 9500:", binarySearch(wrong, 9500));
console.log("numeric sort:", right.join(" "), "-> find 9500:", binarySearch(right, 9500));
console.log("text id:", binarySearch(right, "12000"));

default sort: 12000 150000 45000 800 9500 -> find 9500: -1
numeric sort: 800 9500 12000 45000 150000 -> find 9500: 1
text id: -1

sort() without a comparator sorts numbers as text, where "12000" comes before "150000" and "9500" comes last. The array is sorted, just not the way < compares numbers, so the search for 9500 goes left at 45000 and misses. (It would still find 12000, by luck, which is why a single passing test proves little.) The same happens when names are sorted with localeCompare but searched with <, or sorted case-sensitively and searched case-insensitively. Sort and search must use the same comparison. The last line is the string id from the reasoning box: found by nobody.

Lower and upper bound

Plain binary search answers "is this exact value here?". Real questions are often different:

• "Show every order placed on 3 September." The orders are sorted by time; you need the first order at or after 3 September 00:00 and the first order at or after 4 September.
• "Where does this new order go so the list stays sorted?"
• "Five products cost exactly ₦12,000; list them all." You need the first and the last, not "one of them".

Two functions answer all of these:

• Lower bound: the first index whose value is greater than or equal to the target. If the target is present, that is its first occurrence; if not, it is where the target would be inserted.
• Upper bound: the first index whose value is strictly greater than the target. Everything before it is ≤ the target.

Both can return items.length, meaning "past the end". The number of items equal to the target is upper − lower, and the items in a range [a, b] are those from lowerBound(a) up to, but not including, upperBound(b).

These are written with a half-open range: lo is included and hi is not (hi starts at items.length). The invariant: everything before lo is smaller than the target, and everything from hi on is greater than or equal to it. When lo === hi, that index is the answer. The two loops differ in a single character:

export function lowerBound(items, target, key = (x) => x) {
  let lo = 0;
  let hi = items.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (key(items[mid]) < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

export function upperBound(items, target, key = (x) => x) {
  let lo = 0;
  let hi = items.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (key(items[mid]) <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Compare them with bug 1 and bug 2: here lo < hi and hi = mid are correct, because hi is exclusive. Neither style is right or wrong on its own; mixing them is the bug. The key function lets the same code search objects by one field.

import { lowerBound, upperBound } from "./bounds.js";

const prices = [800, 9500, 12000, 12000, 12000, 45000, 150000];

for (const target of [12000, 10000, 800, 200000, 100]) {
  const lower = lowerBound(prices, target);
  const upper = upperBound(prices, target);
  console.log(`${String(target).padStart(6)}: lower ${lower}, upper ${upper}, count ${upper - lower}`);
}

const insertAt = lowerBound(prices, 10000);
prices.splice(insertAt, 0, 10000);
console.log("after inserting 10000:", prices.join(" "));

 12000: lower 2, upper 5, count 3
 10000: lower 2, upper 2, count 0
   800: lower 0, upper 1, count 1
200000: lower 7, upper 7, count 0
   100: lower 0, upper 0, count 0
after inserting 10000: 800 9500 10000 12000 12000 12000 45000 150000

Finding the insertion point is O(log n), but splice still shifts every later element: inserting into a sorted array is O(n). That is the trade-off that made binary search trees worth building in Trees.

Range queries: orders on one day

The orders are sorted by id and, since ids grow over time, also by placedAt. ISO date strings like 2026-09-03T00:00:00.000Z have fixed widths and sort correctly as text, so they can be compared with < directly.

import { orders } from "./orders.js";
import { lowerBound } from "./bounds.js";

let comparisons = 0;
const placedAt = (order) => {
  comparisons++;
  return order.placedAt;
};

const start = lowerBound(orders, "2026-09-03T00:00:00.000Z", placedAt);
const end = lowerBound(orders, "2026-09-04T00:00:00.000Z", placedAt);
const day = orders.slice(start, end);

console.log(`orders on 3 September: ${day.length}`);
console.log(`first: #${day[0].id} at ${day[0].placedAt}`);
console.log(`last:  #${day.at(-1).id} at ${day.at(-1).placedAt}`);
console.log(`comparisons: ${comparisons} (a scan would make ${orders.length})`);
console.log("check:", day.every((o) => o.placedAt.startsWith("2026-09-03")),
  orders[start - 1].placedAt < "2026-09-03", orders[end].placedAt >= "2026-09-04");

orders on 3 September: 43200
first: #359200 at 2026-09-03T00:00:00.000Z
last:  #488797 at 2026-09-03T23:59:58.000Z
comparisons: 40 (a scan would make 1000000)
check: true true true

Two lower-bound searches, 40 comparisons, however many orders the export holds. Using lowerBound of the next day for the end avoids having to invent a "last possible time on the 3rd". The final line checks the answer from the outside: everything inside is on the 3rd, and the neighbours just outside are not.

Prefix search on sorted names

All names that start with a prefix sit next to each other in a sorted list, starting at the lower bound of the prefix. That is the compact alternative to the trie from Tries:

import { lowerBound } from "./bounds.js";

const names = ["oppo reno", "oraimo freepods", "oraimo powerbank", "oraimo smartwatch", "sharp tv", "sony radio"]
  .sort();

function withPrefix(sorted, prefix, limit = 5) {
  const results = [];
  for (let i = lowerBound(sorted, prefix); i < sorted.length && results.length < limit; i++) {
    if (!sorted[i].startsWith(prefix)) break;
    results.push(sorted[i]);
  }
  return results;
}

console.log(withPrefix(names, "ora").join(" | "));
console.log(withPrefix(names, "s").join(" | "));
console.log(withPrefix(names, "x").length);

oraimo freepods | oraimo powerbank | oraimo smartwatch
sharp tv | sony radio
0

O(L log n) to find the start, then O(k) to read k results, with no memory beyond the sorted array. The names are sorted with the default sort(), which compares by UTF-16 code units, the same way < does, so sort and search agree (bug 4).

Sort once, search many times?

Binary search needs sorted data, and sorting costs O(n log n). If the data is not already sorted, is it worth it? Count comparisons for k searches in n = 100,000 unsorted order totals:

const n = 100_000;
const totals = Array.from({ length: n }, (_, i) => (i * 7919) % 1_000_003);

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

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

const sortCost = Math.round(n * Math.log2(n));
const sorted = [...totals].sort((a, b) => a - b);
for (const k of [1, 10, 100, 1000]) {
  linear = 0;
  binary = 0;
  for (let q = 0; q < k; q++) {
    const target = totals[(q * 104_729 + 50_000) % n];
    linearFind(totals, target);
    binaryFind(sorted, target);
  }
  console.log(`${String(k).padStart(4)} searches: linear ${linear}, sort (about ${sortCost}) + binary ${binary}`);
}

   1 searches: linear 50001, sort (about 1660964) + binary 17
  10 searches: linear 712815, sort (about 1660964) + binary 155
 100 searches: linear 5108650, sort (about 1660964) + binary 1556
1000 searches: linear 50136500, sort (about 1660964) + binary 15663

The sort's cost is estimated as n log₂ n instead of counted, because Array.prototype.sort makes a different number of comparisons in different JavaScript engines. For a single search, sorting first is a loss. After a few dozen searches it wins, and after a thousand it is not close. The arithmetic: k linear searches cost about k × n/2, sorting costs about n log₂ n, so sorting pays off once k is more than about 2 log₂ n, which is 34 searches here. The rule of thumb: if you will search the same data more than a few dozen times, sort it once (or keep it sorted). If you only ever need exact lookups, a Map from id to order beats both with O(1) average per lookup, at the price of extra memory and no range queries.

Testing a search

Search functions are perfect for testing against a reference: linear search is obviously correct, so every binary search, lower bound and upper bound must agree with it. The inputs that matter are the edges: the empty array, one element, targets below the minimum, above the maximum, between two values, and runs of duplicates. Random small arrays with a small range of values produce all of those, many times over.

import { lowerBound, upperBound } from "./bounds.js";

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

const refLower = (a, t) => { const i = a.findIndex((x) => x >= t); return i === -1 ? a.length : i; };
const refUpper = (a, t) => { const i = a.findIndex((x) => x > t); return i === -1 ? a.length : i; };

function check(label, ok) {
  console.log(`${ok ? "PASS" : "FAIL"} ${label}`);
}

check("empty array", binarySearch([], 1) === -1 && lowerBound([], 1) === 0 && upperBound([], 1) === 0);
check("one element", binarySearch([5], 5) === 0 && binarySearch([5], 4) === -1 && binarySearch([5], 6) === -1);

let seed = 3;
const random = () => (seed = (seed * 16807) % 2147483647) / 2147483647;
let failures = 0;
let cases = 0;
for (let round = 0; round < 500; round++) {
  const items = Array.from({ length: Math.floor(random() * 12) }, () => Math.floor(random() * 8)).sort((a, b) => a - b);
  for (let target = -1; target <= 8; target++) {
    cases++;
    const found = binarySearch(items, target);
    const foundOk = found === -1 ? !items.includes(target) : items[found] === target;
    if (!foundOk) failures++;
    if (lowerBound(items, target) !== refLower(items, target)) failures++;
    if (upperBound(items, target) !== refUpper(items, target)) failures++;
  }
}
check(`${cases} random cases agree with linear search`, failures === 0);

PASS empty array
PASS one element
PASS 5000 random cases agree with linear search

Notice the check for binarySearch: with duplicates it may return any matching index, so the test accepts any index that holds the target, and for −1 demands that the target really is absent. Testing "returns index 2" would reject a correct implementation. Each of the six bugs above makes this test fail; try pasting one in.

Searching in production

• Databases do this for you. An index on orders.id or orders.placed_at is a B-tree, a many-way cousin of binary search, so WHERE placed_at >= '2026-09-03' AND placed_at < '2026-09-04' is two "lower bound" descents and a scan between them. Write the range in exactly that half-open form; it is the same reasoning as lowerBound, and it avoids missing orders at 23:59:59.5.
• Cursor pagination is a lower bound. "The next 50 orders after id 734,512" is WHERE id > 734512 ORDER BY id LIMIT 50: find the position, read forward. Unlike OFFSET, it stays fast on page 10,000 and does not skip or repeat items when new orders arrive.
• Binary search is a debugging tool. git bisect binary-searches your commit history for the commit that introduced a bug: 1,000 commits take about 10 test runs. The same idea finds which of 500 config changes broke a build.
• Keep the precondition true. A sorted array stays sorted only if every insert uses the lower bound (or re-sorts). One push of an out-of-order item silently breaks every later search. Wrap the array in a small class that owns inserts, or assert sortedness in tests.
• Compare consistently. Sort and search with the same comparison: numeric comparators for numbers, one locale and options for localeCompare, and the same normalisation for text.
• Binary search on the answer. The halving idea works on anything monotonic, not just arrays: "what is the smallest number of delivery vans that can finish today's orders by 18:00?" can be answered by binary-searching over the number of vans. That is the subject of Binary search as a pattern, later in this course.

Practice

import { lowerBound, upperBound } from "./bounds.js";

const products = [
  { name: "USB cable", kobo: 250_000 }, { name: "Earbuds", kobo: 1_200_000 },
  { name: "Phone case", kobo: 1_200_000 }, { name: "Power bank", kobo: 1_200_000 },
  { name: "Smartwatch", kobo: 4_500_000 }, { name: "Blender", kobo: 5_000_000 },
  { name: "Speaker", kobo: 5_000_001 },
];
const price = (p) => p.kobo;

const from = lowerBound(products, 1_200_000, price);
const to = upperBound(products, 1_200_000, price);
console.log("at ₦12,000:", products.slice(from, to).map((p) => p.name).join(", "));

const count = upperBound(products, 5_000_000, price) - lowerBound(products, 1_000_000, price);
console.log("between ₦10,000 and ₦50,000:", count);

at ₦12,000: Earbuds, Phone case, Power bank
between ₦10,000 and ₦50,000: 5

import { lowerBound } from "./bounds.js";

const slots = [9 * 60, 10 * 60 + 30, 12 * 60, 15 * 60, 17 * 60 + 30];
const clock = (m) => `${String(Math.floor(m / 60)).padStart(2, "0")}:${String(m % 60).padStart(2, "0")}`;

function nearestSlot(slots, wanted) {
  const i = lowerBound(slots, wanted);
  if (i === 0) return slots[0];
  if (i === slots.length) return slots.at(-1);
  const before = slots[i - 1];
  const after = slots[i];
  return wanted - before <= after - wanted ? before : after;
}

for (const wanted of ["07:15", "11:15", "11:16", "13:30", "20:00"]) {
  const [h, m] = wanted.split(":").map(Number);
  console.log(`${wanted} -> ${clock(nearestSlot(slots, h * 60 + m))}`);
}

07:15 -> 09:00
11:15 -> 10:30
11:16 -> 12:00
13:30 -> 12:00
20:00 -> 17:30

import { upperBound } from "./bounds.js";

const history = [
  { from: "2026-08-01T00:00:00Z", kobo: 1_500_000 },
  { from: "2026-08-20T09:00:00Z", kobo: 1_350_000 },
  { from: "2026-09-01T00:00:00Z", kobo: 1_600_000 },
];

function priceAt(history, time) {
  const i = upperBound(history, time, (change) => change.from) - 1;
  return i < 0 ? undefined : history[i].kobo;
}

for (const time of ["2026-07-15T12:00:00Z", "2026-08-20T09:00:00Z", "2026-08-31T23:59:59Z", "2026-09-10T08:00:00Z"]) {
  const kobo = priceAt(history, time);
  console.log(time, kobo === undefined ? "not on sale yet" : `₦${(kobo / 100).toLocaleString("en-NG")}`);
}

2026-07-15T12:00:00Z not on sale yet
2026-08-20T09:00:00Z ₦13,500
2026-08-31T23:59:59Z ₦13,500
2026-09-10T08:00:00Z ₦16,000

Recap

• Linear search is O(n) and needs nothing from the data. Use it (and find, findIndex, findLast, some, includes) for unsorted data, small arrays, one-off searches and conditions. Always handle "not found".
• Binary search on sorted data halves the range each step: O(log n), about 20 looks for a million items. Write the invariant first: if the target exists, it is between lo and hi.
• The classic bugs live at the edges: a loop condition that does not match the range, a branch that does not shrink it, a fractional or overflowing middle, and data sorted by a different comparison than the search uses.
• Lower bound (first ≥) and upper bound (first >) give first and last occurrences, counts, insertion points, ranges, prefix matches and "nearest" answers, all in O(log n).
• Sorting costs O(n log n), so sort first only when you will search many times; a Map beats both for exact lookups, and a database index does all of it for data on disk.
• Test searches against linear search on random small arrays with duplicates, and accept any correct answer.

Next: Sorting builds the algorithms that produce the sorted data binary search depends on, and measures them against each other.