Linear Search and Binary Search
The two fundamental searching strategies — check everything, or repeatedly halve — and the one precondition binary search absolutely requires.
What you'll learn
- Implement linear search and state its O(n) worst-case complexity
- Implement binary search correctly, including the midpoint and bounds updates
- State precisely why binary search requires sorted input, and what happens if that precondition is violated
Prerequisites
Explanation
Linear search checks every element in order until it finds the target or exhausts the input — simple, requires no precondition on the data at all (unsorted input is fine), and O(n) in the worst case (the target is last, or absent), O(1) in the best case (the target is first). It's the correct, sometimes only, choice when data isn't sorted and sorting it first (an O(n log n) cost, covered next lesson) wouldn't be worth it for a single search.
Binary search is the divide-and-conquer strategy from the previous lesson, applied to searching: check the middle element; if it's the target, done; if the target is smaller, discard the entire right half and repeat on the left half; if larger, discard the left half and repeat on the right. Each comparison eliminates half the remaining candidates, giving O(log n) — for a million elements, roughly 20 comparisons worst case, versus linear search's up to a million.
The one absolute precondition binary search requires, and the reason it isn't simply "always better" than linear search: the data must already be sorted. The entire algorithm's correctness depends on being able to conclude "the target isn't in the discarded half" purely from one comparison against the midpoint — a conclusion that's only valid if every element on one side is guaranteed smaller (or larger) than the midpoint, which unsorted data does not guarantee at all. Running binary search on unsorted data doesn't throw an error or clearly fail — it can silently return the wrong answer, or report "not found" for a target that's actually present, because the halves it's discarding aren't actually guaranteed empty of the target. This is exactly why "is this data sorted?" is the first question to ask before reaching for binary search, and why sorting once (O(n log n)) to enable many subsequent binary searches (O(log n) each) is a common, worthwhile tradeoff, while sorting purely to do one single search usually isn't (linear search's O(n) on unsorted data beats O(n log n) sort + O(log n) search for exactly one lookup).
Example
Binary search's midpoint-and-halve pattern, with explicit bounds tracking.
function binarySearch(sortedArr, target) {
let low = 0, high = sortedArr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (sortedArr[mid] === target) return mid;
if (sortedArr[mid] < target) low = mid + 1; // target must be in the right half, if anywhere
else high = mid - 1; // target must be in the left half, if anywhere
}
return -1; // exhausted the search space -- not present
}
const sorted = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sorted, 7)); // 3 -- found in a couple of comparisons
console.log(binarySearch(sorted, 4)); // -1 -- correctly reports absence
// On UNSORTED data, the same algorithm can silently give a wrong answer:
const unsorted = [7, 1, 13, 3, 9, 5, 11];
console.log(binarySearch(unsorted, 5)); // NOT reliable -- the sortedness assumption is violatedTry it yourself
Run binarySearch on the unsorted array for a target you KNOW is present, and see it incorrectly report -1.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write linearSearch(arr, target) returning the index of target's first occurrence, or -1 if absent. Works on any array, sorted or not.
Checks: finds a target in the middle · finds the first occurrence when the value repeats · returns -1 for a missing target · handles an empty array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write binarySearch(sortedArr, target) returning the target's index, or -1 if absent. Must work correctly on an empty array, a single-element array, and when the target is smaller than every element or larger than every element.
Checks: finds a target in a normal sorted array · handles an empty array · handles a single matching element · handles a single non-matching element · handles a target smaller than the entire array · handles a target larger than the entire array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Running binary search on unsorted data -- it doesn't error, it silently returns wrong results, since the entire algorithm's correctness depends on the sortedness precondition holding.
- Using low < high instead of low <= high as the loop condition -- this off-by-one can cause binary search to miss the correct answer when the search space narrows to exactly one remaining candidate.
- Sorting an array purely to enable a single binary search -- the O(n log n) sort cost dominates, making it slower overall than a single O(n) linear search on the original unsorted data.
Knowledge check
Takeaway
Linear search needs no precondition and costs O(n); binary search needs sorted input and costs O(log n) — but violating that precondition doesn't produce an error, it silently produces wrong answers, which is what makes checking it before reaching for binary search non-negotiable.
Summary
Linear search checks every element, O(n) worst case, works on any input order. Binary search repeatedly halves the search space, O(log n), but strictly requires sorted input — an unmet precondition causes silent incorrect results, not a visible failure. Sort-then-search only pays off when amortized across multiple searches.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.