Searching algorithms
Suppose a row of cards is in front of us and we want the card carrying 11. Searching means deciding whether a matching card exists and, if it does, finding a position where it appears. Checking every card is one way to answer. But if the row is already in order, could that order tell us which positions cannot contain 11?
01Linear search: know exactly what has been ruled out
The target is the value we want. A position tells us where a card sits; it is different from its value. We number positions from 1 in the display. Many programming languages number them from 0, but that changes labels, not the search reasoning. Inspect the first card. If its value matches the target, stop; otherwise rule out that position and move to the next.
Before each step, every earlier card has been checked and failed to match. Every unchecked card is still possible. This statement remains true after each failed comparison, so if we reach the end, there really is no match. It is the reason we can trust “not found”; we did not merely stop because we felt we had searched long enough.
No card has been inspected yet. The outlined range contains every place the target could still be.
Change the arrangement to “Mixed” and repeat. The method still works because it never assumed an order. Set the target to 10 to inspect an absent value. Then choose “Small to large” again and set the target to 2. Now it is the first card, so a match needs only one comparison. If several cards match, this left-to-right method returns the first one.
02Binary search: explain why half can be discarded
Now keep the cards in nondecreasing order: each card is no larger than the next. Suppose the middle card is 9 and the target is 11. Every card left of that 9 is at most 9, so none can be 11. We may discard the middle and everything left of it together. If the middle is greater than the target, the same reasoning discards the middle and everything right of it.
We retain only the range where a match could still be. Inspect its middle next, even though that position need not be the middle of the original row. With two middle choices, this demonstration takes the left one. After a mismatch, the inspected middle is excluded too, so the range must get smaller. When the range is empty, the target is absent. A match stops immediately; with duplicates, that need not be the first matching position.
No card has been inspected yet. The outlined range contains every place the target could still be.
Try “Mixed”. The experiment stops us from applying the discard rule, because we no longer know that everything left is smaller. For example, in the mixed row a middle value of 7 does not tell us which side contains 2. Ordering is the evidence that justifies discarding a half; the mere act of picking a middle is not enough.
03Why does the amount of work grow differently?
For linear search with cards, a last-position match or an absent value needs comparisons. Doubling the number of cards doubles that worst-case work. The best case remains one comparison when the first card matches. These describe different inputs, so they do not contradict each other.
For binary search, count how many positions at most can be distinguished with a limited number of comparisons. Zero comparisons can handle only an empty list. One comparison can test one middle position. With two comparisons, the first middle accounts for one position and each side can have one more, giving . With three, each side can have three, giving .
If is that capacity for comparisons, we have and . The pattern is : it holds at zero, and substituting the previous value gives , so each next case follows. To cover positions, choose the smallest whole number for which . This capacity tells us that fewer comparisons cannot always suffice. We still need to check that choosing the middle can achieve the bound.
Suppose and . Remove the middle card we inspect. If is odd, each side has cards. If is even, the larger side has cards; because is odd, an even within the bound is at most . In either case each side has at most cards. Therefore, after a failed comparison, the remaining side fits the capacity of more comparisons. Repeat this reasoning until no comparisons remain, when the range must be empty. A match can stop sooner. This proves the bound is sufficient too. For eight cards, three comparisons cannot always work, but four always suffice.
Binary search also assumes we can reach a middle position directly, as in an array: a row of indexed storage locations. If reaching the middle requires walking through many links, few value comparisons alone do not guarantee little total work. And if the data is unordered, sorting it first costs work. For just one search, checking each item can be the more sensible task; for repeated searches on unchanged data, paying once for ordering can be useful.
See how sorting creates the needed order04Use the rule and explain what it permits
Read the reasoning
The first middle is position 4, carrying 9. Discard positions 1–4 because all are smaller than 14. The remaining positions are 5–8; their left middle is position 6, carrying 14. We find it after two comparisons.
Read the reasoning
We have just checked that its value is not the target. Keeping it adds no possible match and can stop the interval shrinking when only one position remains. Removing it preserves all genuine possibilities while guaranteeing progress.
Read the reasoning
Five comparisons have capacity , so 31 cards fit. For 32 cards, some target or unsuccessful search needs a sixth comparison, since five levels have only 31 middle positions to inspect.
