Finding one item in a collection is among the oldest problems in computing, and it shows up everywhere: a username among millions of accounts, a product by its id, a single word in a dictionary. How you search decides whether the answer comes back instantly or after an uncomfortable pause. The same is true of sorting — putting items into a predictable order is the precondition that unlocks a fundamentally faster kind of search.
This lesson implements the two foundational searches and a classic sorting algorithm, then weighs each with the Big-O vocabulary you already have. The aim is not to memorise code; it is to recognise, from the shape of the loops alone, why one approach scales and another collapses under load.
flowchart LR A["arr 0: 3"] --> B["arr 1: 7"] --> C["arr 2: 5"] --> D["arr 3: 9"] C --> E["target 5 found at index 2"] style C fill:#1e7f3d,color:#fff style E fill:#1e7f3d,color:#fff
Linear search: check each in turn
The simplest search is the one you do by eye: start at the beginning, compare each item to your target, and stop when you find it or run out of items. In code that is a single loop, and its cost is honest — if the array holds n items, the worst case is n comparisons, so linear search is O(n).
That cost is perfectly fine for small collections, and it is the only choice when the data has no order. But it scales badly. Searching a million records means a million comparisons in the worst case; repeat that on every keystroke of a search box and the interface freezes. The escape is to arrange the data so that each comparison rules out far more than a single item.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
console.log(linearSearch([4, 2, 7, 1], 7));
console.log(linearSearch([4, 2, 7, 1], 9));
Binary search: halve the range
If the array is already sorted, one comparison can eliminate half of the remaining items at once. That is the insight behind binary search. You keep two indices, lo and hi, marking the inclusive range still under consideration. Each step inspects the middle element; if it equals the target you are done, if it is too small you raise lo above the middle, and if it is too large you lower hi below it. The range halves every time, so the worst case needs only about twenty comparisons for a million items.
The precondition is non-negotiable: binary search works only on sorted data. Hand it an unsorted array and it can return the wrong answer without raising any error, which is far more dangerous than a crash.
flowchart TD S["sorted array: 1 3 5 7 9 11"] --> M["check the middle value"] M -->|"too small"| R1["drop the left half<br/>keep 7 9 11"] M -->|"too large"| L1["drop the right half<br/>keep 1 3"] M -->|"equal"| F["done: return the index"] R1 --> M2["halve what remains and repeat"] style F fill:#1e7f3d,color:#fff
function binarySearch(arr, target) {
let lo = 0;
let 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 sorted = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(sorted, 7));
console.log(binarySearch(sorted, 4));
Sorting: put things in order
Sorting rearranges items so that each one comes before the next according to some rule, usually smallest to largest. A sorted array is what makes binary search possible in the first place, and it makes a hundred other tasks easier too: spotting duplicates, merging two datasets, or rendering a leaderboard.
The classic teaching algorithm is bubble sort. It walks the array repeatedly, swapping any adjacent pair that sits in the wrong order, and after enough passes the largest values migrate to the end. It is easy to write and easy to cost: the outer loop runs n times, the inner loop also runs about n times, and those multiply to O(n²). For real work you should reach for the built-in sort, which uses a tuned O(n log n) algorithm — but you have to drive it correctly, and that is where JavaScript's most common sorting bug hides.
flowchart TD A["sorting families"] --> B["bubble sort: O(n²)"] A --> C["built-in sort: O(n log n)"] B --> D["simple, but slow on big data"] C --> E["fast: use this in real code"] style C fill:#1e7f3d,color:#fff style B fill:#b91c1c,color:#fff
function bubbleSort(arr) {
const a = arr.slice();
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
const tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
return a;
}
console.log(bubbleSort([3, 1, 2]));
Choosing the right search
A faster algorithm is not automatically the right one. Binary search needs the array sorted first, and sorting itself costs O(n log n), so if you will search only once, a plain linear scan of the unsorted data is genuinely cheaper than sorting plus binary search. The payoff arrives when you query the same collection many times: pay the sorting cost once, then reap logarithmic lookups on every query afterward. That trade-off is exactly why databases maintain indexes.
The same judgement applies to memory. Linear and binary search both use O(1) extra space — a few variables — which is why they fit so neatly inside a single function. Sorting algorithms vary more here: some rearrange in place using almost no extra room, while others build a fresh sorted copy. Read the loops, ask what each pass costs, and let the actual workload, not the elegance of the algorithm, make the decision.
What does this print? Remember the callout: sort() with no comparator orders elements as strings. An array prints as compact JSON.
const nums = [10, 2, 1, 30]; nums.sort(); console.log(nums);
With no comparator, sort converts each number to a string.
String order is lexicographic, so '10' comes before '2'.
The full order is 1, 10, 2, 30 — printed as compact JSON.
Write linearSearch(arr, target) that returns the index of the first item equal to target, or -1 if it is not present.
function linearSearch(arr, target) {
// return the index of target, or -1
}
Loop i from 0 to arr.length - 1 and compare arr[i] to target.
Return i as soon as you find a match.
If the loop ends with no match, return -1.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
This binary search can loop forever when the target sits in the upper half. The line that raises the lower bound is wrong — it does not move past the element it just ruled out. Fix that one line so every test passes.
function binarySearch(arr, target) {
let lo = 0;
let 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;
} else {
hi = mid - 1;
}
}
return -1;
}
When arr[mid] < target, the middle element cannot be the target, so lo must move past it.
Write lo = mid + 1, not lo = mid — otherwise lo and mid coincide and the window never shrinks.
The hi branch is already correct: hi = mid - 1.
function binarySearch(arr, target) {
let lo = 0;
let 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;
}
Binary search halves the remaining range on every step. What is its worst-case time complexity on a sorted array of n elements?
Each comparison throws away half the range, so the number of steps is the number of times you can halve n — that is log n. It only works because the array is sorted.
Write twoSumSorted(numbers, target) that returns true if any two distinct elements of a sorted array add up to target, and false otherwise. Use two pointers: one at the start and one at the end, moving them inward based on whether the current sum is too small or too large.
function twoSumSorted(numbers, target) {
// use a left pointer and a right pointer
}
Start left at 0 and right at numbers.length - 1.
If numbers[left] + numbers[right] equals target, return true.
If the sum is too small, move left up; if too large, move right down.
function twoSumSorted(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return true;
if (sum < target) left++;
else right--;
}
return false;
}
Recap
- Linear search scans item by item and costs O(n); it works on any data.
- Binary search halves the range each step and costs O(log n), but it needs sorted input.
- Sorting costs at least O(n log n); bubble sort is a clear O(n²) teaching example.
sort()orders elements as strings unless you pass a numeric comparator such as(a, b) => a - b.- Search once with linear; sort once and binary-search many times when queries repeat.
Next you will meet hash tables and the Map object, which turn the O(n) work of finding a key into an average O(1) lookup.