Searching

Strip away the domain details and an enormous share of what programs do is search: find the user with this id, the save file with this name, the opcode handler for this instruction, the string at this offset. This lesson is short on new machinery, you own all the structures involved, and long on a single contrast that shows complexity analysis paying its rent: the gap between O(n) and O(log n), and the exact price of crossing it.

Linear search: the default that always works

Walk the collection from the front, compare each element with the target, stop on a match or at the end. That is linear search, and its virtue is that it assumes nothing: unsorted data, any structure you can iterate, no preparation. Its costs are the case-analysis example you already dissected in the complexity lessons: best case 1 comparison, average about n over 2 for a uniformly placed target, worst case all n, so O(n) with an early exit that helps exactly when luck does. For small collections, or ones searched once, this is genuinely the right algorithm, and every language's built-in find on arrays and lists is exactly this scan.

Linear search is looking for a word in a book with no index by reading every page in order. It works, always, on any book. It is just proportional to the book. The rest of this lesson is about what an index, or an alphabetized layout, buys you, and what it costs to maintain.

Binary search: paying for order, collecting log n

Now suppose the data is sorted, and the structure supports O(1) access by index, an array. Binary search: compare the target against the middle element. Equal, done. Target smaller, the entire upper half is impossible, discard it. Larger, discard the lower half. Either way, one comparison eliminated half the candidates; repeat on the survivor half. From n candidates to 1 takes as many halvings as it takes doublings to grow from 1 to n, which is log base 2 of n: about 10 comparisons for a thousand elements, about 30 for a billion. This is the O(log n) rung of the ladder made concrete, and the guessing-game structure of it, higher, lower, found, is precisely the descent you watched a balanced BST perform last lesson: the BST is binary search frozen into pointers.

Watch the visualizer's window: low and high squeeze from a thousand candidates to one in eight guesses, each comparison discarding hundreds of elements unexamined. That unexamined is the entire magic. Linear search earns its answer by looking at things; binary search earns most of its answer by proving it never needs to look.

The precondition is the price

Binary search's speed is rented, not owned, and the rent has two clauses. First, sorted order: on unsorted data the discard step's logic is simply false, the target could be anywhere, and the algorithm returns confident nonsense. Sorting costs O(n log n), the next lesson's subject, so binary search pays off when data is searched repeatedly, sorted once and queried many times, not for a single lookup, where the scan is cheaper than the sort. Second, O(1) random access: jumping to the middle must be free. Arrays deliver that; linked lists do not, walking to the middle of a list costs O(n) before the first comparison, wiping out the entire advantage. Preconditions like these are the fine print of every complexity claim, and checking them is the difference between using analysis and reciting it.

The implementation is also famously boobytrapped for such a short function. The loop must maintain its invariant, the target, if present, lies within low to high, and every exit from a comparison must shrink the window: low = mid + 1 and high = mid - 1, the plus and minus one excluding the middle element just proven wrong. Write low = mid and a two-element window where mid rounds down to low can stop shrinking: the search spins forever on the boundary. Off-by-one errors in this family shipped in production standard libraries for years, including a famous overflow bug in computing the midpoint of large ranges. The challenge below hands you the infinite-loop variant; the playground's step cap will catch it in the act.

The whole search toolbox, in one view

• Unsorted array or list, searched once: linear scan, O(n). No preparation beats no preparation.
• Sorted array, searched repeatedly: binary search, O(log n) per lookup after an O(n log n) sort.
• Frequent exact-key lookups with inserts arriving constantly: hash map, O(1) average, order forfeited.
• Ordered queries, ranges, nearest keys, under constant inserts: balanced BST, O(log n) for everything, sorted iteration free.
• Reachability and shortest paths in networks: not value search at all, BFS and DFS at O(V + E), last lesson's tools.

Reading that table closely shows the structures of this level converging: hash maps and search trees are not alternatives to searching, they are search algorithms crystallized into memory layouts, the halving of binary search living in tree shape, the direct jump of hashing living in bucket arithmetic. Choosing a data structure largely is choosing which searches your program will run fast.

Searching in protected code

Reverse engineering, at its working level, is search. The Level 5 lessons on reading strings first are grep runs, linear scans over bytes, and the reason string obfuscation exists is to make that cheap scan return nothing. Analysts binary-search too, not always over arrays: the classic technique for locating which code change or which byte region triggers behavior is bisection, halving a candidate range by testing the midpoint, O(log n) experiments instead of O(n). Defenders should assume both speeds are available to attackers: anything findable by a scan will be found in linear time, anything bisectable will be found in logarithmic time, and protection budgets should be spent accordingly, on moving secrets out of scan range entirely rather than merely deeper into the file.

Linear search assumes nothing and costs O(n). Binary search costs O(log n) but rents its speed: sorted data plus O(1) indexing, and an implementation where every step provably shrinks the window. Hash maps and BSTs are these two searches solidified into structures. Match the search to the question shape, and remember attackers are running searches too.

Frequently asked questions