What this module covers: Every search technique so far in Foundation has been O(n) — a full scan, a two-pointer sweep, a sliding window. This module introduces the first O(log n) technique: binary search, which works whenever data is sorted (or has an equivalent monotonic property), and its variants — finding boundaries, searching rotated data, and finding a peak — that all reuse the same halving idea.
The Core Idea: Halving, Not Scanning
Binary search works on sorted data by repeatedly checking the middle element and discarding the half of the search space that can't contain the answer:
typescript
Each comparison eliminates half of whatever's left, not just one element. Starting from n elements, after one comparison there are n/2 candidates left, then n/4, then n/8 — the number of halvings needed to get down to a single candidate is log₂(n). At a million elements, that's roughly 20 comparisons — not a million, not even a thousand. This is the O(log n) complexity class from Module F-1's table, made concrete.
Analogy: Binary search is how you actually look up a name in a phone book (if you've ever seen one) or find a word in a physical dictionary — you don't start at page 1. You open to the middle, see you've overshot or undershot, and repeat on the correct half. Nobody scans a dictionary front to back.
The one hard requirement: the data must be sorted, or have some equivalent monotonic property (a "yes/no" answer that flips exactly once as you scan across the range) — binary search has no way to know which half to discard on unsorted data, because there's no guarantee about what's on either side of the midpoint.
Finding the First or Last Occurrence
Plain binary search finds a match, but stops as soon as it finds one — if the target appears multiple times, which one you get back is unspecified. Finding the first occurrence specifically requires a small but important tweak: don't stop on a match, keep searching left for an earlier one.
typescript
The last occurrence is the mirror image — record the match, then search right instead of left. Both variants stay O(log n); the only change is what you do on a match, not the halving logic itself.
Searching a Rotated Sorted Array
A sorted array that's been rotated (e.g. [4, 5, 6, 7, 0, 1, 2] — sorted, then rotated at index 4) isn't fully sorted anymore, but it has a useful property: at least one half of any split is still sorted, and you can tell which half by comparing the endpoints.
typescript
The key check, nums[left] <= nums[mid], determines which side of the current window is guaranteed sorted (a rotation can only break the order at one point, so one side of any split must still be in order). Once you know which side is sorted, you can apply ordinary binary search logic to decide whether the target could be in that sorted half — and if not, it must be in the other, unsorted-looking half, which gets the same treatment on the next iteration.
Finding a Peak Element
A "peak" is an element strictly greater than both its neighbors. Binary search applies here too, even though the array isn't sorted at all — because you can still make a directional decision at each midpoint:
typescript
If nums[mid] > nums[mid + 1], the sequence is descending at that point, which guarantees a peak exists at mid or earlier (values can't keep descending forever without having risen from somewhere). If it's ascending instead, a peak must exist further right. This is the more general lesson of this section: binary search doesn't require full sortedness — it requires that you can always determine, from one comparison, which half definitely contains what you're looking for.
Where This Shows Up in Your Stack
PostgreSQL B-Tree index lookups are binary search, structurally — a B-Tree (Module A-13 covers the full structure) is organized precisely so that each level of the tree lets the engine discard a large fraction of remaining rows with one comparison, giving O(log n) lookups on an indexed column instead of an O(n) sequential scan.
git bisect is binary search applied to commit history: given a known-good and known-bad commit, it checks out the midpoint commit, asks you (or a test script) "good or bad?", and halves the remaining range — finding the exact commit that introduced a regression in O(log n) checks instead of testing every commit one by one.
Rotated-array search patterns show up conceptually in circular buffers and ring-based data structures (Module F-7's circular queue) — knowing which "half" of a wrapped structure is contiguous is the same reasoning used above.
A time-based key-value store — "what was the value of this key at or before timestamp T?" — stores each key's value history sorted by timestamp and binary searches for the latest entry at or before T, rather than scanning the full history. This is close in spirit to how databases resolve "what did this row look like at this point in time" under MVCC-style versioning (covered for PostgreSQL specifically in the postgresql-in-depth course).
Summary
Binary search eliminates half the remaining search space on every comparison, giving O(log n) instead of O(n) — the difference between ~20 comparisons and a million, at scale.
It requires sortedness, or an equivalent monotonic property — some way to guarantee, from one comparison, which half can be safely discarded.
Finding the first/last occurrence requires continuing to search past the first match found, in the direction of earlier/later occurrences, rather than stopping immediately.
Rotated sorted arrays are still searchable in O(log n) by determining which half of any split remains properly ordered, and applying standard binary search logic within that half.
Peak-finding shows binary search works even on unsorted data, as long as a directional decision (ascending vs. descending) can be made at each midpoint.
This closes out Foundation. The Foundation Capstone — DSA in Production: The Node.js Event Loop, Call Stack, and Queues — ties Modules F-6 (Stacks) and F-7 (Queues) directly to the runtime you've been writing code in this whole time, before Practitioner begins with recursion.
Knowledge Check
Why does binary search require the input to be sorted (or have an equivalent monotonic property), rather than working on arbitrary unordered data?
In searchRotated, what is the purpose of the check nums[left] <= nums[mid]?
In findFirstOccurrence, why does the function set right = mid - 1 immediately after finding a match at mid (sorted[mid] === target), instead of returning mid right away?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionbinarySearch(sorted:number[], target:number):number{let left =0;let right = sorted.length -1;while(left <= right){const mid = left + Math.floor((right - left)/2);// avoids overflow vs (left + right) / 2if(sorted[mid]=== target)return mid;if(sorted[mid]< target) left = mid +1;// target must be in the right halfelse right = mid -1;// target must be in the left half}return-1;// not found}
functionfindFirstOccurrence(sorted:number[], target:number):number{let left =0;let right = sorted.length -1;let result =-1;while(left <= right){const mid = left + Math.floor((right - left)/2);if(sorted[mid]=== target){ result = mid;// record this match... right = mid -1;// ...but keep searching left for an earlier one}elseif(sorted[mid]< target){ left = mid +1;}else{ right = mid -1;}}return result;}findFirstOccurrence([1,2,2,2,3,4],2);// 1 (the first index where 2 appears)
functionsearchRotated(nums:number[], target:number):number{let left =0;let right = nums.length -1;while(left <= right){const mid = left + Math.floor((right - left)/2);if(nums[mid]=== target)return mid;if(nums[left]<= nums[mid]){// Left half [left..mid] is sortedif(nums[left]<= target && target < nums[mid]) right = mid -1;else left = mid +1;}else{// Right half [mid..right] is sorted insteadif(nums[mid]< target && target <= nums[right]) left = mid +1;else right = mid -1;}}return-1;}searchRotated([4,5,6,7,0,1,2],0);// 4
functionfindPeakElement(nums:number[]):number{let left =0;let right = nums.length -1;while(left < right){const mid = left + Math.floor((right - left)/2);if(nums[mid]> nums[mid +1]){ right = mid;// a peak exists at mid or somewhere to its left}else{ left = mid +1;// a peak exists somewhere to the right of mid}}return left;// left === right, pointing at a peak}findPeakElement([1,2,3,1]);// 2 (index of value 3)