SESSION 035 — Search & Sort

CONCEPTS.UNLOCKED

🔎

Linear Search

Check every item one by one → O(n). Simple, works on unsorted data. For 500 images, that's up to 500 comparisons. For 1 million? Up to 1 million.

✂

Binary Search

Only works on sorted data → O(log n). Each step eliminates half the remaining options. 1 million items? Only ~20 comparisons. Dramatically faster.

↕

Sorting

JavaScript's .sort(compareFn) with comparison functions. Sort by name (localeCompare), by date (newest first), by size (largest first). The foundation for binary search.

⚖

Comparison Functions

(a, b) => a - b for numbers. (a, b) => a.localeCompare(b) for strings. Return negative (a first), zero (equal), or positive (b first).

📊

O(log n) — The Power of Halving

log₂(1,000,000) ≈ 20. Searching 1 million items takes ~20 comparisons. Each step eliminates half. This is why Google can search billions of pages in milliseconds.

🗄

Why Databases Do This Better

Databases use B-trees and indexes — the same binary search principle, but optimized for disk access. Preview of what you'll build with backend databases in Phase 3.

HANDS-ON.TASKS

Implement Linear Search

▶

function linearSearch(images, query) {
  return images.filter(img =>
    img.name.toLowerCase().includes(query.toLowerCase())
  );
}

.filter() checks every single element — that's O(n). For fuzzy, "contains" search, linear is actually the right choice. Binary search only helps for exact matches on sorted data.

Sort the Gallery

▶

// Sort by name
images.sort((a, b) => a.name.localeCompare(b.name));

// Sort by date (newest first)
images.sort((a, b) => new Date(b.date) - new Date(a.date));

// Sort by size (largest first)
images.sort((a, b) => b.size - a.size);

.sort() mutates the original array. If you need to keep the original order, sort a copy: [...images].sort(...). The comparison function must return a negative, zero, or positive number.

Implement Binary Search

▶

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

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const comparison = sortedImages[mid]
      .name.localeCompare(targetName);

    if (comparison === 0) return mid;
    if (comparison < 0) low = mid + 1;
    else high = mid - 1;
  }

  return -1; // Not found
}

The array MUST be sorted first. Each iteration halves the search space: 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. That's only ~9 steps for 500 items.

Benchmark: Linear vs Binary

▶

Dataset Size	Linear O(n)	Binary O(log n)
500 items	500 comparisons	~9 comparisons
5,000 items	5,000 comparisons	~13 comparisons
50,000 items	50,000 comparisons	~16 comparisons
1,000,000 items	1,000,000 comparisons	~20 comparisons

From 50,000 to 1 million items: linear search gets 20× slower. Binary search adds only 4 more comparisons. The gap widens exponentially.

Build the Gallery UI

▶

Build the complete gallery interface:

Component	Function
Search bar	Live filtering as you type (linear search)
Sort dropdown	Name, Date, Size, Type
Image grid	Thumbnail + name + metadata
Result count	"Showing 12 of 500 images"

Close the Ticket

▶

git switch -c feature/PIXELCRAFT-023-gallery-search
git add src/scripts/ src/styles/
git commit -m "Add gallery search and sort with binary search (PIXELCRAFT-023)"
git push origin feature/PIXELCRAFT-023-gallery-search
# PR → Review → Merge → Close ticket ✅

CS.DEEP-DIVE

Binary search is O(log n).

Searching 1 million items takes ~20 comparisons. Each step eliminates HALF the remaining options.

// The same principle behind:

B-trees          → database indexes
"20 Questions"   → 2²⁰ = 1 million items
Bisection debug  → "bug is in the first half
                   or second half?"
Git bisect       → find the commit that
                   broke something

// The logarithm is one of the most
// powerful mathematical concepts in CS.

REF.MATERIAL

VIDEO

Binary Search in 100 Seconds — Fireship

Fireship

The fastest possible intro to binary search: the algorithm, why it's O(log n), and when to use it vs linear search.

BINARY SEARCHQUICKESSENTIAL

VIDEO

15 Sorting Algorithms Visualized — Timo Bingmann

Timo Bingmann

Mesmerizing visual and auditory representation of 15 sorting algorithms. Watch how different algorithms approach the same problem.

SORTINGVISUALSATISFYING

ARTICLE

Array.prototype.sort() — MDN

Mozilla Developer Network

Complete sort() reference: comparison functions, stability, in-place mutation, and sorting objects by property.

SORTMDNREFERENCE

ARTICLE

Binary Search — Khan Academy

Khan Academy

Interactive step-by-step binary search tutorial with visualizations. Try it yourself with guided exercises.

BINARY SEARCHINTERACTIVE

ARTICLE

Binary Search Algorithm — Wikipedia

Wikipedia

The complete picture: history, pseudocode, proof of correctness, variations (lower bound, upper bound), and relation to binary search trees.

BINARY SEARCHTHEORYCS

SEARCH & SORT