COMP5112 Chap.2 Searching Arrays Efficiently
Searching Arrays Efficiently
Information creates the speed-up
Linear search works on an unsorted array and may inspect every item. Binary search gains logarithmic time only because sorted order lets one comparison discard half the remaining interval.
The chapter traces inclusive low, mid and high boundaries, covers successful and unsuccessful searches, and then places lookup cost beside the cost of initially sorting and later maintaining order during insertion and deletion.
Linear search needs almost no structural promise. Starting at one end, it compares successive values until it finds the target or reaches the array boundary.
The best case uses one comparison, while an unsuccessful or final-position search inspects every element. State whether the routine returns a Boolean, an index, or a special absent value. Duplicate data introduces another contract choice: any matching position, the first match, the last match, or the complete range of matches.
Binary search maintains a candidate interval in a sorted array.
With inclusive endpoints, low and high name positions that may still contain the target. The middle comparison either succeeds, raises low beyond mid, or lowers high below mid. The update must exclude the compared position so that the interval strictly shrinks.
For a failed search, the proof of absence is low greater than high; stopping after one unequal comparison does not establish that the target is missing.
A table is the safest trace format. Give low, mid, high, the middle value, the comparison result, and the next interval on each row. Decide in advance whether positions are zero-based or one-based and apply the same system to midpoint arithmetic and the returned answer.
When the interval has even length, the chosen rounding convention affects which middle position is visited but not correctness if every subsequent boundary update matches it.
The logarithmic bound follows from discarded information. After k unsuccessful comparisons, at most n divided by two to the power k candidates remain.
The process ends once that quantity falls below one, giving a number of steps proportional to log base two of n. This argument relies on sorted order and a shrinking interval. Applying the routine to unsorted data, or leaving mid inside the next interval, removes the premise behind both correctness and the bound.
Fast lookup can require expensive maintenance.
If a collection is searched once, sorting first may cost more than a linear scan. If it is searched many times without change, one sort followed by logarithmic searches can repay that cost. Insertions into a sorted array may need linear shifting even though the insertion position is found quickly.
Compare a full workload by combining build, search and update frequencies rather than declaring binary search universally superior.
Boundary-search variants provide richer answers. A lower bound finds the first position whose value is not less than the key; an upper bound finds the first position whose value is greater.
Their difference counts equal entries, and both return useful insertion boundaries when the key is absent. These versions often use a half-open interval, so their conditions cannot be mixed casually with inclusive pseudocode. Test below-minimum, duplicated, above-maximum and empty-array cases to validate the contract.
What this chapter covers
- 01
Linear search on unsorted arrays
- 02
Binary-search preconditions
- 03
Inclusive boundary traces
- 04
Successful and failed lookup
- 05
Logarithmic interval shrinkage
- 06
Search and update workload trade-offs
Worked example · free
Trace a failed binary search
- 2Record the first interval and middle comparison.
- 2Update the correct boundary.
- 2Identify the empty interval.
Key terms
- Linear Search
- A sequential inspection that works without sorted order.
- Binary Search
- A sorted-array search that discards half the candidate interval each step.
- Candidate Interval
- The inclusive range of positions that can still hold the target.
- Precondition
- A requirement that must hold before an operation is valid.
Searching Arrays Efficiently FAQ
Why must binary-search data be sorted?
The comparison with the middle value rules out a whole side only when position order agrees with key order. Without that property, a smaller target could appear on either side and discarding half would be unjustified.
What causes an infinite binary-search loop?
A boundary update that leaves the tested middle position inside an unchanged interval. After inequality, exclude mid itself and verify that the new candidate interval is strictly smaller.
When can linear search be the better design?
When data is small, unsorted and changes frequently, or when only a few searches occur. Sorting and maintaining order have costs that binary lookup alone does not show in a workload comparison.
Exam move
Trace one present target and three absent targets: below the minimum, above the maximum and between adjacent values. Record indices rather than only the remaining values. Alternate inclusive and half-open versions on separate sheets, writing each loop condition and update in full. Add duplicated keys and derive lower and upper bounds.
Finish by calculating a break-even workload that includes initial sorting, repeated lookups and later insertions, so the data-structure recommendation reflects total use rather than lookup time alone.
Working through Searching Arrays Efficiently in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Searching Arrays Efficiently question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
