Difficulty: Beginner | Prerequisites: Arrays, basic loop constructs
Searching is one of the most fundamental operations in computer science: given a collection of data, find a specific element (or confirm it is absent). The two core approaches, sequential search and binary search, differ dramatically in efficiency, and understanding why is your first real encounter with algorithmic complexity. This material also introduces growth-rate functions, which give you the vocabulary to compare algorithms at scale. If you have not yet covered arrays and basic iteration, review those first.
Sequential search checks every element one by one; binary search repeatedly halves a sorted collection. Binary search is far faster on large datasets, but it requires the data to be sorted first. Growth-rate functions (constant, linear, polynomial, exponential) let you describe and compare how algorithms scale.
Sequential search (linear search)
A search algorithm that examines each element in a collection one at a time, from start to finish, until the target is found or every element has been checked. Think of it as reading a phone book line by line from page one.
Binary search
A search algorithm that works on sorted data by repeatedly comparing the target to the middle element and discarding the half that cannot contain it. Think of it as opening a dictionary near the middle and deciding whether to flip forward or backward.
Comparison (in the context of search)
A single check of one element against the target value. When a question asks "how many comparisons," it is asking how many elements you had to look at.
Growth-rate function
A mathematical description of how an algorithm's resource usage (time or space) increases as the input size grows. In simple terms, it tells you whether doubling your data makes things twice as slow, four times as slow, or astronomically worse.
Constant function – O(1)
Growth that does not change regardless of input size. Accessing an array element by index is constant time.
Linear function – O(n)
Growth that scales directly with input size. Sequential search is linear: double the data, roughly double the work.
Polynomial function – O(n²), O(n³), etc.
Growth where the work increases by a power of the input size. Many basic sorting algorithms fall here.
Exponential function – O(2ⁿ)
Growth that doubles (or more) with each additional input element. This becomes impractical very quickly and is the fastest-growing category you will encounter in this course.
Start at the first element, compare it to the target.
If it matches, you are done. If not, move to the next element.
Continue until you either find the target or exhaust the entire collection.
Worst case: you check every single element (the target is last, or not present at all).
Example: Given {1, 4, 6, 7, 9, 10, 14}, finding 9 requires checking 1, 4, 6, 7, then 9 – that is 5 comparisons (4 non-matches plus the match itself).
Example: Searching for 11 in the same array means checking all 7 elements before concluding it is not present.
Requires the data to be sorted beforehand.
Look at the middle element. If it matches, done.
If the target is greater, discard the lower half and repeat on the upper half.
If the target is smaller, discard the upper half and repeat on the lower half.
Continue until the target is found or the remaining slice is empty.
Example: Given {1, 4, 6, 7, 9, 10, 14}, searching for 9:
Middle element is 7. Since 9 > 7, search the upper half: {9, 10, 14}.
Middle of that slice is 10. Since 9 < 10, search the lower portion: {9}.
9 is found. Total comparisons: 3 (checked 7, then 10, then 9).
The search ends when one of two things happens:
The middle value equals the target (success).
There are no more elements to check, i.e. the "first" pointer exceeds the "last" pointer, or the slice length reaches 0 (target not found).
This is a common exam question. "When the value is found" is only half the answer; you must also explain the failure condition.
Constant – O(1)
Linear – O(n)
Polynomial – O(n²)
Exponential – O(2ⁿ)
This ranking matters because it determines which algorithms remain practical at scale. An exponential algorithm on even moderately large input can take longer than the age of the universe.
Binary search maximum comparisons: For an array of n elements, binary search needs at most ⌈log₂(n)⌉ + 1 comparisons.
For 7 elements: ⌈log₂(7)⌉ + 1 = 3 + 1 = 4 comparisons maximum.
Sequential search comparisons:
Target present at position k (1-indexed): k comparisons.
Target absent: n comparisons (must check every element).
Binary search is the principle behind how a database index locates a record without scanning every row, and why looking up a word in a physical dictionary is fast even though it contains tens of thousands of entries. Sequential search is what your email client does when you search an unsorted inbox.
"Binary search always checks fewer elements." Only true when the data is sorted. On unsorted data, binary search does not work at all.
"Sequential search for a missing element takes n − 1 comparisons." It takes n comparisons, because you must check every element to confirm absence.
"Binary search comparisons" and "binary search slices" are the same count. Each slice involves a comparison at the midpoint, but be precise about what the question is asking: number of elements examined, or number of halving steps.
"Growth rates only matter for huge datasets." Even at modest sizes (a few thousand elements), the difference between O(n) and O(n²) is noticeable, and O(2ⁿ) is typically unusable past about 30 elements.
⚠️ You will be asked to trace a binary search step by step, showing which element is checked at each stage and which half is discarded.
⚠️ Know both termination conditions for binary search (found the target, or the slice is empty). Stating only "when the value is found" will lose marks.
⚠️ Sequential search comparison counts: include the final comparison where the target is actually found (position 5 means 5 comparisons, not 4).
⚠️ Growth-rate ranking (constant < linear < polynomial < exponential) is a standard exam question.
True or false: Binary search can be used on an unsorted array. Answer: False. The array must be sorted.
Fill in the blank: In sequential search, if the target is not in an array of 10 elements, the number of comparisons is ___. Answer: 10.
True or false: O(n²) grows faster than O(2ⁿ). Answer: False. Exponential growth outpaces polynomial growth.
Q: Given the sorted array {1, 4, 6, 7, 9, 10, 14}, how many comparisons does binary search need to find 9? Show your working.
A: Check middle (7) – 9 > 7, take upper half {9, 10, 14}. Check middle (10) – 9 < 10, take lower portion {9}. Check 9 – found. Three comparisons total.
Q: Using sequential search on the same array, how many comparisons to find 9?
A: Check 1, 4, 6, 7, 9. Five comparisons (9 is the fifth element).
Q: What condition causes a binary search to end without finding the target?
A: When the search range is empty, meaning the "first" index exceeds the "last" index (or the slice length is 0).
Q: Rank these from slowest to fastest growth: exponential, constant, polynomial, linear.
A: Constant, linear, polynomial, exponential.
This connects directly to sorting algorithms, because binary search requires sorted data, so choosing an efficient sort matters. Growth-rate analysis reappears throughout the course as Big-O notation, which you will use to evaluate every algorithm going forward.
sequential search, linear search, binary search, search algorithm, comparison count, growth rate, Big-O, O(1), O(n), O(n²), O(2ⁿ), constant time, linear time, polynomial time, exponential time, divide and conquer search, sorted array search, APCS searching, algorithm efficiency, time complexity ranking