DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Search Techniques: Sequential, Binary, and Tree Search
The gap between "checking every item" and "eliminating half each time" is enormous at scale.
🔍 Sequential vs Binary Search
SequentialCheck every element one by one — O(n), works on ANY list, sorted or not.
BinaryOnly works on SORTED data — repeatedly compare against the middle element, eliminating half the remaining search space each time. O(log n).
Worked example — binary search for 23 in [4,8,15,16,23,42,56]:
Compare 23 to middle (16, index 3): 23>16, search RIGHT half
Compare 23 to middle of [23,42,56] → 42: 23<42, search LEFT half
Compare 23 to 23: FOUND — 3 comparisons total
(vs sequential search which would take 5 comparisons)
Tree search (searching a BST) applies this exact same "compare and eliminate half" logic, but along the tree's actual branching structure rather than an array's midpoint.
💡 Practice binary search step-by-step on a 7-8 element sorted array, showing which half gets eliminated at each comparison — a guaranteed numerical.
How big the gap gets
The difference is easy to underrate at small sizes and impossible to ignore at large ones.
Note the last column. A thousandfold increase in data adds only ten comparisons to binary search, because each one halves the remaining space and 2¹⁰ ≈ 1000. Searching a billion sorted items takes 30 comparisons — which is why sorted structures underpin every database index.
💡 At n = 7 the two are equal, which is the honest version of the comparison. Binary search wins by an enormous margin at scale and by nothing at all on small data — the same "constants matter at small n" lesson as in the sorting chapters.
The catch: binary search needs sorted data
This is the judgement the complexity comparison omits. Sorting is not free, and it costs more than a single sequential search.
For n = 1000:
sort once ≈ n·log₂n ≈ 9,965 operations
one sequential search ≈ n/2 = 500 operations
k sequential searches: 500k
sort then k binary: 9,965 + 10k
Break-even: about k = 20 searches.
So for a one-off search on unsorted data, sequential search is the right answer and sorting first is a net loss. Sorting pays only when the data will be searched many times, or when it is kept sorted as it is built rather than sorted specially.
💡 The exam framing: "you must search an unsorted array once — which algorithm?" The answer is sequential, and saying so with the reason earns more than reciting that binary search is O(log n). The complexity is only half the decision.
Why binary search needs random access
Binary search must jump straight to the middle element. On an array that is one index calculation; on a linked list it means walking from the head, so reaching the middle is already O(n) and the whole advantage evaporates.
This is why a sorted linked list cannot be binary searched efficiently, and why trees exist: a balanced BST gives the same halving behaviour on a pointer-based structure that supports cheap insertion, which a sorted array does not.
💡 Three structures, three trade-offs: a sorted array gives O(log n) search and O(n) insertion; a linked list gives O(1) insertion and O(n) search; a balanced tree gives O(log n) for both, which is why it is the usual answer when you need both operations to be fast.
Syllabus points
Sequential search
Binary search (numerical)
Tree search
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.