SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 25
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 25 of 30

Searching and sorting questions

binary search (first and last occurrence)merge sortsort objects by two keys with a comparator

These are the notes for JavaScript Coding Questions, episode 25, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Last episode we wrote recursion. Today we use it, for searching and sorting. Three questions that come up in almost every interview: find the first and last position of a value with binary search, write merge sort yourself, and sort a list of objects by two keys (marks, then name). On the way, two comparators that look right quietly do the wrong thing, and a merge that forgets its leftovers loses numbers.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. A few programs measure time with console.time / console.timeEnd, which print how long the code between them took. Timings differ on every machine and every run: we show the numbers we got; yours will be different, but the gap between the slow and the fast version will be just as large.

First: binary search in one minute

A friend thinks of a number from 1 to 100. You guess 50. "Higher," they say. In one guess you threw away half the numbers (1 to 50). You guess 75. "Lower." Half of what's left is gone again (76 to 100). You always guess the middle of what's left, and you never need more than 7 guesses.

  • Binary search: find a value in a sorted list by looking at the middle, then throwing away the half that can't contain it, again and again.
  • Sorted: in order, smallest first (or largest first). Binary search only works on sorted data: "higher" tells you something only because the numbers are in order.
  • lo and hi: the first and last index of the range we still have. mid is the middle index, Math.floor((lo + hi) / 2) (Math.floor rounds down to a whole number).
  • Linear search: checking items one by one from the start. For n items that's up to n steps, O(n).
  • O(log n): work that grows like the number of times you can halve n before reaching 1 (log₂ n). Binary search is O(log n). (Big-O describes how the work grows as the input grows.)
function guess(secret, low, high) {
  let lo = low, hi = high, tries = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    tries++;
    if (mid === secret) {
      console.log(`guess ${mid}: yes! (${tries} guesses)`);
      return tries;
    }
    if (mid < secret) {
      console.log(`guess ${mid}: higher`);
      lo = mid + 1;
    } else {
      console.log(`guess ${mid}: lower`);
      hi = mid - 1;
    }
  }
}
guess(65, 1, 100);
let worst = 0;
for (let s = 1; s <= 100; s++) {
  let lo = 1, hi = 100, t = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    t++;
    if (mid === s) break;
    if (mid < s) lo = mid + 1; else hi = mid - 1;
  }
  worst = Math.max(worst, t);
}
console.log("worst case for 1 to 100:", worst, "guesses");
console.log("log2(100) =", Math.log2(100).toFixed(2));
console.log("log2(1,000,000) =", Math.log2(1000000).toFixed(2));
guess 50: higher
guess 75: lower
guess 62: higher
guess 68: lower
guess 65: yes! (5 guesses)
worst case for 1 to 100: 7 guesses
log2(100) = 6.64
log2(1,000,000) = 19.93
  • "Higher" means the secret is right of mid: lo = mid + 1. "Lower" means left: hi = mid - 1. We skip mid itself, because we already know it's wrong.
  • The loop runs while lo <= hi, that is, while the range still has at least one number.
  • The worst case for 100 numbers is 7 guesses, and log₂ 100 ≈ 6.64 rounds up to 7. For a million numbers: log₂ ≈ 19.93, so 20 guesses.

How big is the difference? Here we count the steps to find the last item of a sorted list, one by one versus with binary search:

function linearSteps(arr, target) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    steps++;
    if (arr[i] === target) break;
  }
  return steps;
}
function binarySteps(arr, target) {
  let lo = 0, hi = arr.length - 1, steps = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    steps++;
    if (arr[mid] === target) break;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return steps;
}
for (const n of [100, 10000, 1000000]) {
  const arr = Array.from({ length: n }, (_, i) => i * 2);
  const target = arr[n - 1];
  console.log(`n = ${n}: linear ${linearSteps(arr, target)} steps, binary ${binarySteps(arr, target)} steps`);
}
n = 100: linear 100 steps, binary 7 steps
n = 10000: linear 10000 steps, binary 14 steps
n = 1000000: linear 1000000 steps, binary 20 steps

Array.from({ length: n }, (_, i) => i * 2) makes [0, 2, 4, …], a sorted list of n numbers. A hundred times more data costs linear search a hundred times more steps; binary search only adds about 7 steps.

Q1: First and last position of a value

Problem. A shoe shop keeps its stock in a sorted list of sizes: [3, 7, 7, 7, 7, 7, 9, 12]. Find the first and the last position (index) of size 7. Answer: first 1, last 5.

Think out loud. - Why both? Because then the count is last - first + 1 = 5 - 1 + 1 = 5: five pairs of size 7. - The list is sorted, so think binary search. - Edge cases: a size that isn't in stock (5), an empty list, and a list where every pair is the same size ([7, 7, 7]).

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
const sizes = [3, 7, 7, 7, 7, 7, 9, 12];
console.log(binarySearch(sizes, 7));
console.log(binarySearch(sizes, 12), binarySearch(sizes, 5));
3
7 -1

12 is at index 7 and 5 isn't there (-1, the usual "not found" answer): those two are right. But 3? Index 3 is a 7, but it's not the first 7 (index 1) and not the last one (index 5).

Why? Binary search stops at the first match it lands on: if (arr[mid] === target) return mid. The first mid is Math.floor((0 + 7) / 2) = 3, which happens to be a 7, so it returns at once. With repeated values, it answers "is there a 7?", not "where do the 7s start?".

Fix: on a match, remember it and keep searching

Walk along the shoe rack. You find a size 7 in the middle: write down where it is. But don't stop: there may be more 7s to the left, so keep searching the left half (hi = mid - 1). If you find another 7, write that one down instead. When the range is empty, the last position you wrote down is the first 7. For the last 7, the same trick the other way: after a match, keep searching the right half (lo = mid + 1).

function findEdge(arr, target, first) {
  let lo = 0, hi = arr.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
const sizes = [3, 7, 7, 7, 7, 7, 9, 12];
const f = findEdge(sizes, 7, true), l = findEdge(sizes, 7, false);
console.log(f, l, "count:", l - f + 1);
console.log(findEdge(sizes, 5, true), findEdge([], 7, false));
console.log(findEdge([7, 7, 7], 7, true), findEdge([7, 7, 7], 7, false));
1 5 count: 5
-1 -1
0 2
  • ans starts at -1, so if no match is ever found we return "not found".
  • The flag first (true or false) picks the direction to keep going after a match.
  • First 1, last 5, count 5. Size 5: -1.
  • The empty list: -1, because hi starts at -1, so lo <= hi is false and the loop never runs.
  • All sevens: first 0, last 2.

Complexity: each search still halves the range on every step, so O(log n) time, even when the whole list is sevens. Space O(1) (a few variables, whatever the size of the list). Two searches are still O(log n): 2 × 20 steps for a million items.

Trap: walking left from the match. A common "fix" is to find any 7, then step left while the previous item is also 7. It gives the right answer, but on a list of a million 7s it walks half the list:

function findFirstLinear(arr, target) {
  let i = binarySearch(arr, target);
  if (i === -1) return -1;
  let steps = 0;
  while (i > 0 && arr[i - 1] === target) { i--; steps++; }
  return { index: i, steps };
}
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
let edgeSteps = 0;
function findEdge(arr, target, first) {
  let lo = 0, hi = arr.length - 1, ans = -1;
  while (lo <= hi) {
    edgeSteps++;
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
const allSevens = new Array(1000000).fill(7);
console.log("walk left:", findFirstLinear(allSevens, 7));
console.log("findEdge:", findEdge(allSevens, 7, true), "in", edgeSteps, "steps");
walk left: { index: 0, steps: 499999 }
findEdge: 0 in 19 steps

new Array(1000000).fill(7) makes a million 7s. Walking left: 499,999 steps, that's O(n). findEdge: 19 steps.

Q2: Write merge sort

Problem. A school has answer sheets in random order of roll numbers. Sort them, smallest first, without the built-in arr.sort(). [42, 7, 19, 3, 25] → [3, 7, 19, 25, 42]. It must stay fast for a board exam: 20,000 sheets.

Think out loud. - Correct is not enough: it has to be fast. - Edge cases: an empty list, and repeated roll numbers.

Attempt: bubble sort

Bubble sort: compare each neighbour pair, and swap them if they're in the wrong order. After each pass, the biggest remaining number has "bubbled" to the end.

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++)
    for (let j = 0; j < a.length - 1 - i; j++)
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
  return a;
}
console.log(bubbleSort([42, 7, 19, 3, 25]));
const rolls = [];
for (let i = 0; i < 20000; i++) rolls.push((i * 7919) % 100003);
console.time("bubble 20,000");
bubbleSort(rolls);
console.timeEnd("bubble 20,000");
[ 3, 7, 19, 25, 42 ]
bubble 20,000: 3.257s

(The time is what we got on our machine; yours will differ, but expect seconds.)

  • [...arr] copies the array (the spread syntax), so we don't change the caller's list.
  • [a[j], a[j + 1]] = [a[j + 1], a[j]] swaps two items (destructuring assignment).
  • (i * 7919) % 100003 makes 20,000 different numbers in a mixed-up order, the same every run (% is the remainder after division).

Five numbers, sorted. But 20,000 took over three seconds, for one sort. Why? Two nested loops over n items: about n² / 2 comparisons. For 20,000 that's about 200 million comparisons. Double the sheets and it takes four times as long. That's O(n²).

The merge sort idea: two teachers, two sorted piles

  1. Split the pile in two; each teacher sorts half. How? The same way: split again.
  2. Keep splitting until each pile has one sheet. One sheet is already sorted: that's the base case.
  3. Merge two sorted piles: look at the top sheet of each pile, take the smaller one, repeat. You never look further down than the top.
  4. When one pile runs out, the other pile is already sorted, so put all of it on, as it is: the leftovers.

Attempt: merge, without the leftovers

i walks the left pile, j the right pile. While both have sheets, push the smaller top sheet. (left[i++] uses left[i], then adds 1 to i.)

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out;
}
console.log(merge([2, 5, 8, 9], [1, 3, 4]));
[ 1, 2, 3, 4 ]

Where are 8 and 9? The loop stops as soon as either pile is empty (&& needs both conditions). The right pile ran out after 4, so 8 and 9 were still waiting on the left. We forgot the leftovers, step 4 of the story.

Fix: add the leftovers, then split and merge

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
console.log(merge([2, 5, 8, 9], [1, 3, 4]).join(", "));
console.log(mergeSort([42, 7, 19, 3, 25]));
console.log(mergeSort([]), mergeSort([5, 5, 1]));
const rolls = [];
for (let i = 0; i < 20000; i++) rolls.push((i * 7919) % 100003);
console.time("merge 20,000");
mergeSort(rolls);
console.timeEnd("merge 20,000");
1, 2, 3, 4, 5, 8, 9
[ 3, 7, 19, 25, 42 ]
[] [ 1, 5, 5 ]
merge 20,000: 24.034ms

(Again, your time will differ; expect a few to a few tens of milliseconds.)

  • left.slice(i) is what's left of the left pile (from index i to the end); right.slice(j) the same for the right. Only one of them has anything left; the other is []. concat joins arrays into a new one.
  • mergeSort: zero or one item, return it (the base case). Otherwise split at mid, sort both halves recursively (episode 24), and merge them.
  • All seven numbers come out of the merge. The five roll numbers are sorted, the empty list stays empty, the repeated 5s stay.
  • 20,000 sheets in about 24 milliseconds instead of over 3 seconds: more than 100 times faster here.

Complexity: we halve the list about log₂ n times (log₂ 20,000 ≈ 14.3, so 15 levels), and every level merges all n items once. So O(n log n) time. Space is O(n) for the merged arrays (merge sort is not in place: it builds new arrays). Equal values keep their original order, because of the <= (on a tie, the left pile wins), so merge sort is stable (see "Going further").

Q3: Sort objects by two keys

Problem. A class teacher has a list of students, each an object with a name and marks. Make the rank list: highest marks first; when two students have the same marks, by name, A to Z. And don't change the original list: the attendance register uses that order.

The list: Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82, as objects like { name: "Ravi", marks: 82 }. Expected: Asha 91, Kabir 91, Anil 82, Neha 82, Ravi 82.

How a comparator decides. arr.sort(compare) takes a comparator: a function that gets two items, a and b, and returns a number: - negative: a should come first; - positive: b should come first; - zero: a tie, keep them in the order they came in.

That's why b.marks - a.marks gives highest first: if b has more marks, the result is positive, so b goes first. A second key is a rule for ties: only when the marks are equal, compare the names.

Attempt 1: return a.marks < b.marks

const students = [
  { name: "Ravi", marks: 82 }, { name: "Asha", marks: 91 },
  { name: "Neha", marks: 82 }, { name: "Kabir", marks: 91 },
  { name: "Anil", marks: 82 },
];
const ranked = [...students].sort((a, b) => a.marks < b.marks);
console.log(ranked.map(s => s.name + " " + s.marks).join(", "));
Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82

Ravi 82 first, Asha 91 second: nothing moved. It's the input order. Why? A comparator must return a number. true becomes 1 and false becomes 0, never negative. So sort is never told "a comes first". Zero says "equal", one says "b first", and the order falls apart. ([...students] copies the list first, and .map(...).join(", ") turns the result into one line of text.)

Attempt 2: subtract both keys

const students = [
  { name: "Ravi", marks: 82 }, { name: "Asha", marks: 91 },
  { name: "Neha", marks: 82 }, { name: "Kabir", marks: 91 },
  { name: "Anil", marks: 82 },
];
const byRank = (a, b) =>
  b.marks - a.marks || a.name - b.name;
const ranked = [...students].sort(byRank);
console.log(ranked.map(s => s.name + " " + s.marks).join(", "));
console.log("Ravi" - "Anil");
Asha 91, Kabir 91, Ravi 82, Neha 82, Anil 82
NaN
  • x || y gives x if it's truthy, else y. 0 is falsy, so when the marks are equal (b.marks - a.marks is 0), the name decides. That part is a good idea.
  • The marks are right now: Asha and Kabir first. But the 82s come out Ravi, Neha, Anil: the input order, not A to Z.
  • And "Ravi" - "Anil" is NaN ("Not a Number"). Minus only works on numbers; two words can't be turned into numbers, so the result is NaN. sort treats NaN like 0, a tie, so the names were never compared. Asha before Kabir was only luck: they came in that order.

Fix: localeCompare for strings

a.localeCompare(b) compares two strings in dictionary order and returns a negative number, a positive number or zero: exactly what sort wants.

const students = [
  { name: "Ravi", marks: 82 }, { name: "Asha", marks: 91 },
  { name: "Neha", marks: 82 }, { name: "Kabir", marks: 91 },
  { name: "Anil", marks: 82 },
];
const byRank = (a, b) =>
  b.marks - a.marks || a.name.localeCompare(b.name);
const ranked = [...students].sort(byRank);
console.log(ranked.map(s => s.name + " " + s.marks).join(", "));
console.log(students[0].name, "is still first in the original");
console.log("Asha".localeCompare("Ravi"), "Ravi".localeCompare("Asha"));
Asha 91, Kabir 91, Anil 82, Neha 82, Ravi 82
Ravi is still first in the original
-1 1
  • Highest marks first, ties A to Z: Asha 91, Kabir 91, Anil 82, Neha 82, Ravi 82.
  • Ravi is still first in the original list, because we sorted a copy.
  • "Asha".localeCompare("Ravi") is -1 (Asha comes first); the other way round it's 1.

Complexity: sort in Node does O(n log n) comparisons, and our comparator is constant work, so O(n log n) time. The copy costs O(n) space. Without the copy, sort changes the original array in place (see the quiz). The newer toSorted method (ES2023) returns a sorted copy for you: students.toSorted(byRank).

Why both wrong comparators "do nothing". Here are both boolean versions side by side, with a correct numeric one:

const students = [
  { name: "Ravi", marks: 82 }, { name: "Asha", marks: 91 },
  { name: "Neha", marks: 82 }, { name: "Kabir", marks: 91 },
  { name: "Anil", marks: 82 },
];
const show = list => list.map(s => s.name + " " + s.marks).join(", ");
console.log(Number(true), Number(false));
console.log("a.marks < b.marks:", show([...students].sort((a, b) => a.marks < b.marks)));
console.log("a.marks > b.marks:", show([...students].sort((a, b) => a.marks > b.marks)));
console.log("b.marks - a.marks:", show([...students].sort((a, b) => b.marks - a.marks)));
const r = "Ravi" - "Anil";
console.log(r, r < 0, r > 0, r === 0, Number.isNaN(r));
1 0
a.marks < b.marks: Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82
a.marks > b.marks: Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82
b.marks - a.marks: Asha 91, Kabir 91, Ravi 82, Neha 82, Anil 82
NaN false false false true
  • Both boolean comparators leave this list exactly as it was: with only 0 and 1, sort never hears "a first". (On other inputs they may move some items, but never into a reliable order.)
  • b.marks - a.marks alone sorts the marks, and leaves ties in input order (Ravi, Neha, Anil), because the built-in sort is stable.
  • NaN is not less than 0, not more than 0, not even equal to 0 (it isn't equal to anything, not even itself). Number.isNaN is the way to test for it.

Complexity summary

Task Time Extra space Notes
Linear search O(n) O(1) works on any list
Binary search O(log n) O(1) sorted list only; 1,000,000 → 20 steps
First / last occurrence (findEdge) O(log n) O(1) two binary searches; count = last - first + 1
Find any match, then walk left O(n) worst case O(1) 499,999 steps on a million 7s
Bubble sort O(n²) O(n) here (we copy), O(1) in place 3.257 s for 20,000 on our machine
Merge sort O(n log n) O(n) stable; 24.034 ms for 20,000 on our machine
arr.sort(cmp) O(n log n) sorts in place stable; returns the same array
arr.toSorted(cmp) O(n log n) O(n) returns a new sorted copy
Search insert position (your turn) O(log n) O(1) lo is the answer when the loop ends

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
Return on the first match if (arr[mid] === target) return mid 3 (a 7, not the first 7) it stops at any match ans = mid, then keep searching left or right
Walk left from the match while (arr[i - 1] === target) i-- steps: 499999 on a million 7s O(n) when everything matches findEdge: O(log n)
Binary search on unsorted data binarySearch([12, 3, 9, 7, 25, 1], 3) -1 (3 is at index 1) it throws away the wrong half sort first, or use indexOf
Bubble sort on 20,000 items two nested loops bubble 20,000: 3.257s (our machine) O(n²): about 200 million comparisons merge sort: O(n log n)
Merge without the leftovers return out; [ 1, 2, 3, 4 ] (8 and 9 lost) the loop stops when either pile is empty out.concat(left.slice(i), right.slice(j))
< instead of <= in merge if (key(left[i]) < key(right[j])) 5 Anil, 5 Asha (Asha came first) on a tie the right pile wins <=: keeps merge sort stable
Boolean comparator sort((a, b) => a.marks < b.marks) Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82 (unchanged) true/false → 1/0, never negative b.marks - a.marks
Subtracting strings a.name - b.name NaN, ties stay Ravi, Neha, Anil minus on strings a.name.localeCompare(b.name)
sort() with no comparator on numbers [9, 100, 25, 1000, 3].toSorted() [ 100, 1000, 25, 3, 9 ] the default compares as text (a, b) => a - b
Forgetting that sort is in place const sorted = marks.sort(...) marks is sorted too sort changes and returns the same array [...marks].sort(...) or marks.toSorted(...)

Going further

Count occurrences in O(log n)

The count of a value in a sorted list is last - first + 1, or 0 if it's missing. Here it is next to the simple filter count, on a sorted list of a million sizes:

function findEdge(arr, target, first) {
  let lo = 0, hi = arr.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
function countOf(arr, target) {
  const f = findEdge(arr, target, true);
  if (f === -1) return 0;
  return findEdge(arr, target, false) - f + 1;
}
const sizes = [3, 7, 7, 7, 7, 7, 9, 12];
for (const s of [3, 7, 9, 5, 12]) console.log(`size ${s}: ${countOf(sizes, s)} pairs`);

const big = [];
for (let s = 1; s <= 10; s++) for (let k = 0; k < 100000; k++) big.push(s);
console.time("binary count");
const a = countOf(big, 7);
console.timeEnd("binary count");
console.time("filter count");
const b = big.filter(x => x === 7).length;
console.timeEnd("filter count");
console.log(a, b, big.length);
size 3: 1 pairs
size 7: 5 pairs
size 9: 1 pairs
size 5: 0 pairs
size 12: 1 pairs
binary count: 0.034ms
filter count: 13.425ms
100000 100000 1000000

Both count 100,000 sevens among a million sizes. The timings are ours and will differ on your machine, but the binary count looks at about 40 items, while filter looks at all 1,000,000. filter works on unsorted data too; binary search needs the order.

Binary search on an unsorted list

Binary search doesn't crash on unsorted data. It just gives wrong answers, quietly:

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
const unsorted = [12, 3, 9, 7, 25, 1];
console.log(binarySearch(unsorted, 3), unsorted.indexOf(3));
console.log(binarySearch(unsorted, 25), unsorted.indexOf(25));
const sorted = unsorted.toSorted((a, b) => a - b);
console.log(sorted, binarySearch(sorted, 3), binarySearch(sorted, 25));
-1 1
4 4
[ 1, 3, 7, 9, 12, 25 ] 1 5

Looking for 3: the middle is 9, 3 is smaller, so it throws away the right half, and then the left half's middle is 12... and it never sees the 3 at index 1. It says -1. (indexOf is the built-in linear search.) Finding 25 worked only by luck. After sorting, both are found.

The default sort() compares text

const marks = [9, 100, 25, 1000, 3];
console.log(marks.toSorted());
console.log(marks.toSorted((a, b) => a - b));
console.log(marks.toSorted((a, b) => b - a));
console.log(marks);
console.log("100" < "25");
const names = ["ravi", "Asha", "anil", "Kabir"];
console.log(names.toSorted());
console.log(names.toSorted((a, b) => a.localeCompare(b)));
[ 100, 1000, 25, 3, 9 ]
[ 3, 9, 25, 100, 1000 ]
[ 1000, 100, 25, 9, 3 ]
[ 9, 100, 25, 1000, 3 ]
true
[ 'Asha', 'Kabir', 'anil', 'ravi' ]
[ 'anil', 'Asha', 'Kabir', 'ravi' ]
  • With no comparator, sort and toSorted turn the items into strings and compare them character by character: "100" < "25" is true, because "1" comes before "2". So numbers need (a, b) => a - b (smallest first) or (a, b) => b - a (largest first).
  • toSorted never changes the original: marks is still [ 9, 100, 25, 1000, 3 ]. (sort would have changed it in place, as the quiz shows. ES2023 also added toReversed and toSpliced, the copy versions of reverse and splice.)
  • For strings, the default puts all capital letters before small letters ('Kabir' before 'anil'). localeCompare uses dictionary order: anil, Asha, Kabir, ravi.

The stable sort trick: sort by name, then by marks

A sort is stable if items that compare equal keep their original order. JavaScript's sort and toSorted are guaranteed stable (since ES2019). That gives a second way to sort by two keys: sort by the second key first, then by the first key. The ties of the second sort keep the name order from the first one.

const students = [
  { name: "Ravi", marks: 82 }, { name: "Asha", marks: 91 },
  { name: "Neha", marks: 82 }, { name: "Kabir", marks: 91 },
  { name: "Anil", marks: 82 },
];
const show = list => list.map(s => s.name + " " + s.marks).join(", ");
const byName = students.toSorted((a, b) => a.name.localeCompare(b.name));
console.log("by name:      ", show(byName));
const ranked = byName.toSorted((a, b) => b.marks - a.marks);
console.log("then by marks:", show(ranked));
const oneStep = students.toSorted((a, b) => b.marks - a.marks || a.name.localeCompare(b.name));
console.log("one comparator:", show(oneStep));
console.log("original:     ", show(students));
by name:       Anil 82, Asha 91, Kabir 91, Neha 82, Ravi 82
then by marks: Asha 91, Kabir 91, Anil 82, Neha 82, Ravi 82
one comparator: Asha 91, Kabir 91, Anil 82, Neha 82, Ravi 82
original:      Ravi 82, Asha 91, Neha 82, Kabir 91, Anil 82

Same result both ways, and the original is untouched. The one-comparator version is a single sort, so it's what you'd normally write; the two-sort trick is handy when the user clicks one column header and then another, like in a spreadsheet.

Stable or not: <= versus < in merge

Merge sort is stable because of the <= in merge. Here we sort answer sheets by roll number only (key picks the value to compare), once with <= and once with <:

function merge(left, right, key) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (key(left[i]) <= key(right[j])) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}
function mergeSortBy(arr, key) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSortBy(arr.slice(0, mid), key), mergeSortBy(arr.slice(mid), key), key);
}
const sheets = [
  { roll: 12, name: "Ravi" }, { roll: 5, name: "Asha" },
  { roll: 12, name: "Neha" }, { roll: 3, name: "Kabir" }, { roll: 5, name: "Anil" },
];
console.log(mergeSortBy(sheets, s => s.roll).map(s => s.roll + " " + s.name).join(", "));
function mergeStrict(left, right, key) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (key(left[i]) < key(right[j])) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}
function mergeSortStrict(arr, key) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return mergeStrict(mergeSortStrict(arr.slice(0, mid), key), mergeSortStrict(arr.slice(mid), key), key);
}
console.log(mergeSortStrict(sheets, s => s.roll).map(s => s.roll + " " + s.name).join(", "));
3 Kabir, 5 Asha, 5 Anil, 12 Ravi, 12 Neha
3 Kabir, 5 Anil, 5 Asha, 12 Neha, 12 Ravi

With <=, on a tie the left pile (the earlier items) wins: Asha before Anil, Ravi before Neha, as in the input. With <, the right pile wins ties, and both pairs come out swapped. Still sorted by roll number, but not stable.

Count the comparisons: n² versus n log n

The same bubble sort and merge sort, with a counter instead of a timer. Counts don't depend on the machine:

let comparisons = 0;
function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++)
    for (let j = 0; j < a.length - 1 - i; j++) {
      comparisons++;
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
    }
  return a;
}
function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    comparisons++;
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
for (const n of [5, 1000, 2000, 4000, 20000]) {
  const rolls = [];
  for (let i = 0; i < n; i++) rolls.push((i * 7919) % 100003);
  comparisons = 0;
  bubbleSort(rolls);
  const b = comparisons;
  comparisons = 0;
  mergeSort(rolls);
  console.log(`n = ${n}: bubble ${b}, merge ${comparisons} comparisons`);
}
n = 5: bubble 10, merge 5 comparisons
n = 1000: bubble 499500, merge 8390 comparisons
n = 2000: bubble 1999000, merge 18783 comparisons
n = 4000: bubble 7998000, merge 41546 comparisons
n = 20000: bubble 199990000, merge 252576 comparisons
  • Bubble sort always does exactly n(n - 1) / 2 comparisons: 1000 → 499,500. Doubling n (1000 → 2000 → 4000) makes it 4 times bigger each time: that's O(n²).
  • Merge sort a bit more than doubles each time: that's O(n log n). At 20,000: about 200 million versus about 250 thousand, almost 800 times fewer.
  • For 5 items, 10 versus 5: nobody cares. Big-O matters when n is big.

Mini project: a price filter for a shop

An online shop has a "price between Rs min and Rs max" filter. Sort the products by price once; then every filter is two binary searches:

  • lowerBound(arr, x): the first index whose value is ≥ x (where x would go, to the left of any equal values).
  • upperBound(arr, x): the first index whose value is > x (just past the last x).
  • The products from lowerBound(min) up to (not including) upperBound(max) are exactly the ones in range.

These two use a slightly different style of binary search: hi starts at arr.length (one past the end), and the loop runs while lo < hi. When it stops, lo === hi is the answer. It never returns early, so equal values are handled without an extra flag.

// Price filter for a shop: how many products cost between min and max?
function lowerBound(arr, x) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
function upperBound(arr, x) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
const products = [
  { name: "steel bottle", price: 349 }, { name: "notebook", price: 60 },
  { name: "backpack", price: 899 }, { name: "pen set", price: 120 },
  { name: "lunch box", price: 349 }, { name: "headphones", price: 499 },
  { name: "umbrella", price: 250 }, { name: "water bottle", price: 199 },
];
const byPrice = products.toSorted((a, b) => a.price - b.price || a.name.localeCompare(b.name));
const prices = byPrice.map(p => p.price);
function inRange(min, max) {
  const from = lowerBound(prices, min), to = upperBound(prices, max);
  return byPrice.slice(from, to);
}
for (const [min, max] of [[200, 500], [349, 349], [1000, 2000], [0, 100]]) {
  const found = inRange(min, max);
  console.log(`Rs ${min} to ${max}: ${found.length} ->`, found.map(p => `${p.name} (${p.price})`).join(", ") || "nothing");
}

const many = Array.from({ length: 1000000 }, (_, i) => (i * 7919) % 100003).sort((a, b) => a - b);
console.time("binary range count");
const c1 = upperBound(many, 50000) - lowerBound(many, 20000);
console.timeEnd("binary range count");
console.time("filter range count");
const c2 = many.filter(p => p >= 20000 && p <= 50000).length;
console.timeEnd("filter range count");
console.log(c1, c2);
Rs 200 to 500: 4 -> umbrella (250), lunch box (349), steel bottle (349), headphones (499)
Rs 349 to 349: 2 -> lunch box (349), steel bottle (349)
Rs 1000 to 2000: 0 -> nothing
Rs 0 to 100: 1 -> notebook (60)
binary range count: 0.06ms
filter range count: 48.679ms
300002 300002
  • The products are sorted by price, and ties by name (lunch box before steel bottle): the two-key comparator from Q3.
  • prices is just the numbers, so the binary searches compare plain numbers. slice(from, to) cuts out the matching products.
  • found.map(...).join(", ") || "nothing": an empty list joins to "", which is falsy, so we print nothing.
  • On a million prices, both ways count the same 300,002 products. Two binary searches took 0.06 ms; filter took about 49 ms (our timings; yours will differ). The one-time sort is the price you pay for every fast filter after it.
  • upperBound(arr, x) - lowerBound(arr, x) is also the count of x, another way to write countOf.

Your turn: search insert position (solution)

Problem. A new pair of shoes arrives. Write searchInsert(sizes, target): return the index of target if it's in the sorted list, or the index where it would go to keep the list sorted. For [3, 7, 9, 12]: 9 → 2, 8 → 2, 1 → 0, 15 → 4.

Hint from the video: it's a plain binary search, and when the loop ends, lo is the answer. O(log n).

function searchInsert(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo;
}
const sizes = [3, 7, 9, 12];
for (const t of [9, 8, 1, 15]) console.log(`${t} -> ${searchInsert(sizes, t)}`);
console.log(searchInsert([], 5), searchInsert([7], 7), searchInsert([7], 10));
const stock = [...sizes];
const pos = searchInsert(stock, 8);
stock.splice(pos, 0, 8);
console.log(stock);
9 -> 2
8 -> 2
1 -> 0
15 -> 4
0 0 1
[ 3, 7, 8, 9, 12 ]
  • The only change from the plain binary search: return lo instead of return -1.
  • Why lo? The loop keeps one promise: everything left of lo is smaller than the target, and everything right of hi is bigger. When the loop ends, lo is one past hi, so lo is exactly the first position whose value is bigger: the place to insert. For 8: mid = 1 (7 < 8, lo = 2), mid = 2 (9 > 8, hi = 1), stop: lo = 2.
  • Edge cases: an empty list gives 0; [7] with 7 gives 0; with 10 gives 1 (the end).
  • stock.splice(pos, 0, 8) inserts 8 at pos, removing nothing, so the stock stays sorted: [ 3, 7, 8, 9, 12 ]. (Finding the place is O(log n); splice still moves the later items, O(n).)
  • With repeated values, this returns some matching index (like Q1's attempt). For "the first place it could go", use lowerBound from the mini project.

Practice questions (with solutions)

1. Count inversions with merge sort. An inversion is a pair of positions i < j where arr[i] > arr[j]: two items in the wrong order. Count them in O(n log n). [2, 4, 1, 3, 5] has 3: (2, 1), (4, 1), (4, 3).

Solution
function countInversions(arr) {
  if (arr.length <= 1) return { sorted: arr, count: 0 };
  const mid = Math.floor(arr.length / 2);
  const L = countInversions(arr.slice(0, mid));
  const R = countInversions(arr.slice(mid));
  const out = [];
  let i = 0, j = 0, count = L.count + R.count;
  while (i < L.sorted.length && j < R.sorted.length) {
    if (L.sorted[i] <= R.sorted[j]) out.push(L.sorted[i++]);
    else {
      count += L.sorted.length - i;
      out.push(R.sorted[j++]);
    }
  }
  return { sorted: out.concat(L.sorted.slice(i), R.sorted.slice(j)), count };
}
console.log(countInversions([2, 4, 1, 3, 5]).count);
console.log(countInversions([1, 2, 3]).count, countInversions([3, 2, 1]).count, countInversions([]).count);
console.log(countInversions([5, 5, 1]).count);
3
0 3 0
2

It's merge sort that also returns a count. During the merge, when the right pile's top sheet is smaller, it is smaller than every sheet still in the left pile (the left pile is sorted), so that's L.sorted.length - i inversions at once. A sorted list has 0; a reversed list of 3 has 3 (every pair); [5, 5, 1] has 2 (equal 5s are not an inversion, thanks to <=). Bubble sort does exactly one swap per inversion, so this also tells you how much work bubble sort would do.

2. Search a rotated sorted array. A sorted list was "rotated": [3, 5, 7, 9, 12, 15] became [9, 12, 15, 3, 5, 7]. Find a value's index in O(log n), or -1.

Solution
function searchRotated(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[lo] <= arr[mid]) {
      if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
const rotated = [9, 12, 15, 3, 5, 7];
console.log(searchRotated(rotated, 5), searchRotated(rotated, 12), searchRotated(rotated, 8));
console.log(searchRotated([3, 5, 7], 7), searchRotated([], 1), searchRotated([4], 4));
4 1 -1
2 -1 0

Cut a rotated list in the middle and at least one half is sorted. If arr[lo] <= arr[mid], the left half is sorted: if the target lies between its ends, go left, else go right. Otherwise the right half is sorted: same test on that side. Each step still throws away half: O(log n). It also works on a list that isn't rotated at all ([3, 5, 7]).

3. Sort by three keys. A cricket scorecard: most runs first; same runs, fewer balls first; same runs and balls, by name A to Z.

Solution
const players = [
  { name: "Ravi", runs: 50, balls: 40 }, { name: "Asha", runs: 72, balls: 51 },
  { name: "Neha", runs: 50, balls: 32 }, { name: "Kabir", runs: 50, balls: 32 },
  { name: "Anil", runs: 72, balls: 60 },
];
const order = (a, b) =>
  b.runs - a.runs || a.balls - b.balls || a.name.localeCompare(b.name);
for (const p of players.toSorted(order)) console.log(p.name, p.runs, p.balls);
Asha 72 51
Anil 72 60
Kabir 50 32
Neha 50 32
Ravi 50 40

Chain the keys with ||: each one is only looked at when all the keys before it are 0 (a tie). b - a for "biggest first", a - b for "smallest first", localeCompare for text. Kabir and Neha tie on runs and balls, so the name decides.

Quick quiz

const marks = [9, 100, 25];
const sorted = marks.sort((a, b) => a - b);
console.log(sorted);
console.log(marks);

A) [ 9, 25, 100 ], then [ 9, 100, 25 ] B) [ 100, 25, 9 ], then [ 9, 25, 100 ] C) [ 9, 25, 100 ], then [ 9, 25, 100 ] D) [ 100, 25, 9 ], then [ 9, 100, 25 ]

Answer
[ 9, 25, 100 ]
[ 9, 25, 100 ]

C. a - b sorts smallest first: [ 9, 25, 100 ]. And sort works in place and returns the same array, so marks is sorted too. To keep the original, copy it first ([...marks].sort((a, b) => a - b)) or use marks.toSorted((a, b) => a - b).

Interview questions

  1. What is binary search, and when can you use it? Look at the middle of a sorted range and throw away the half that can't hold the target, until it's found or the range is empty. Only on sorted data. O(log n) time, O(1) space.
  2. How do you find the first and last occurrence? Binary search, but on a match save the index and keep going: left (hi = mid - 1) for the first, right (lo = mid + 1) for the last. Count = last - first + 1. Still O(log n).
  3. Why not find any match and walk left? It's O(n) when many items are equal (499,999 steps on a million 7s).
  4. What does binary search return when the value is missing? Usually -1. But lo at the end is the insert position, which is often more useful.
  5. Why is bubble sort slow? Two nested loops: about n² / 2 comparisons. O(n²): doubling n makes it 4 times slower.
  6. Explain merge sort. Split the list in half, sort each half recursively (one item is the base case), and merge the two sorted halves by repeatedly taking the smaller front item, then adding the leftovers. O(n log n) time, O(n) extra space, stable.
  7. What is a stable sort, and why does it matter? Equal items keep their original order. It lets you sort by one key after another, and keeps ties predictable. JavaScript's sort is stable; merge sort is stable if the merge uses <=.
  8. What must a comparator return? A number: negative if a comes first, positive if b comes first, zero for a tie. Not true/false.
  9. How do you sort objects by two keys? (a, b) => b.marks - a.marks || a.name.localeCompare(b.name): the second key only decides when the first gives 0. Or sort by the second key, then stable-sort by the first.
  10. Why not a.name - b.name? Minus on strings gives NaN, which sort treats as a tie, so the names are never compared. Use localeCompare.
  11. What does [9, 100, 25, 1000, 3].sort() give? [ 100, 1000, 25, 3, 9 ]: without a comparator the items are compared as text. Use (a, b) => a - b for numbers.
  12. sort or toSorted? sort changes the array in place and returns it; toSorted (ES2023) returns a new sorted array and leaves the original alone.

Glossary

Term Meaning
Searching Finding where (or whether) a value is in a collection
Sorting Putting items in order, for example smallest first
Sorted In order; binary search needs sorted data
Linear search Checking items one by one from the start: O(n)
Binary search Look at the middle of a sorted range, throw away the half that can't hold the target, repeat: O(log n)
lo, hi, mid The first index, last index and middle index of the range still being searched
Index The position of an item in an array, starting at 0
-1 (not found) The usual answer when a search finds nothing (like indexOf)
First / last occurrence The smallest / largest index where a value appears in a list
Count of a value last - first + 1 in a sorted list, or 0 when missing
Insert position The index where a value would go to keep a list sorted (lo at the end of binary search)
Lower bound / upper bound The first index with a value ≥ x / > x
Rotated sorted array A sorted list cut in two and the parts swapped: [9, 12, 15, 3, 5, 7]
Big-O How the work grows as the input grows
O(1) The same work whatever the size
O(log n) Work that grows like the number of times you can halve n (20 for a million)
O(n) Work that grows in step with n
O(n log n) n work on each of about log n levels: merge sort, the built-in sort
O(n²) Work that grows with n times n: doubling n makes it 4 times bigger
log₂ n How many times you halve n to reach 1: log₂ 1,000,000 ≈ 20
Bubble sort Repeatedly swap neighbour pairs that are in the wrong order: O(n²)
Merge sort Split in half, sort each half recursively, merge: O(n log n)
Merge Combine two sorted lists into one by taking the smaller front item each time
Leftovers The items still in one list when the other runs out during a merge
Base case The input small enough to answer directly (0 or 1 items for merge sort)
Recursion A function that calls itself on a smaller version of the problem
Inversion A pair of items in the wrong order (i < j but arr[i] > arr[j])
Stable sort A sort where equal items keep their original order
In place Changing the array itself instead of making a new one (sort, reverse, splice)
Comparator A function (a, b) => number that tells sort the order: negative a first, positive b first, zero a tie
arr.sort(cmp) Sorts the array in place and returns the same array; with no comparator it compares as text
arr.toSorted(cmp) ES2023: returns a new sorted array and leaves the original alone
localeCompare a.localeCompare(b): negative, positive or zero by dictionary order; the comparator for strings
NaN "Not a Number": the result of maths that has no number answer, like "Ravi" - "Anil"; not equal to anything
Number.isNaN Tests whether a value is NaN
Truthy / falsy Values that count as true / false in a condition; 0, "" and NaN are falsy
\|\| (or) x \|\| y gives x if it's truthy, else y; used to chain comparator keys
Spread (...) [...arr] copies an array's items into a new array
Destructuring swap [a, b] = [b, a] swaps two values
slice / concat Copy part of an array / join arrays into a new one
splice Insert or remove items in place: arr.splice(pos, 0, x) inserts x at pos
indexOf The built-in linear search: the first index of a value, or -1
filter A new array with the items that pass a test
Math.floor Round down to a whole number
console.time / console.timeEnd Print how long the code between them took; differs per machine and run

Summary

  • Binary search halves the range every step: O(log n), a million items in 20 steps. It only works on sorted data, and on unsorted data it gives wrong answers quietly.
  • For the first or last position, don't return on a match: save it in ans and keep searching left or right. Count = last - first + 1. Still O(log n); walking left from a match is O(n).
  • Bubble sort is O(n²): fine for 5 items, seconds for 20,000.
  • Merge sort: split, sort both halves, merge. The merge must add the leftovers (out.concat(left.slice(i), right.slice(j))), and <= keeps it stable. O(n log n) time, O(n) space.
  • A comparator returns a number, never true/false. Subtract numbers, use localeCompare for strings, and chain keys with ||. "Ravi" - "Anil" is NaN.
  • sort works in place and returns the same array; copy first with [...arr], or use toSorted. With no comparator, sort compares as text: [ 100, 1000, 25, 3, 9 ].
  • Search insert position is a plain binary search that returns lo at the end.
  • Next episode: linked list questions: build a linked list with classes, reverse it, find the middle in one pass, and detect a cycle.