Searching
Finding one value in a collection, and what each assumption about the data buys you.
Searching asks one question of a collection: where is this value, or is it here at all. The whole subject is how much structure you are allowed to assume. With no assumption you check every slot in turn, which is n comparisons in the worst case and about n / 2 on average, and there is nothing to improve.
Sorted order is the assumption worth the most. Comparing against the middle of a sorted array tells you which half the target cannot be in, and halving repeatedly takes log2 n steps: twenty for a million elements, thirty for a billion. The variants change only where the probe lands. Jump search steps sqrt(n) at a time and then scans one block. Exponential search doubles the index until it overshoots, which beats log n when the target is near the front. Interpolation search guesses where the value should sit on a straight line through the range.
None of this is free. Sorting an unsorted array so you can binary search it costs O(n log n), which only pays for itself once you ask enough questions of the same data. For a single lookup on unsorted data, the linear scan is the right answer, not the lazy one.
After this you can
- Write a binary search whose bounds terminate, without guessing at the comparisons
- Say how many probes each search makes on n elements, and on what assumption
- Decide whether sorting first pays for itself, given how many queries follow
- Recognise when exponential or interpolation search beats plain halving, and when it does not
Index 0 holds 5, not 2. Move on.
In this order
- Linear SearchCheck every slot in order. On average half the array, in the worst case all of it.
- Binary SearchCompare with the middle of a sorted array and half of it stops mattering.
- Jump SearchJump sqrt(n) at a time while the block's last value is below the target, then scan one block.
- Exponential SearchDouble the probe index until the value passes the target, then binary search the last doubling: O(log i).
- Interpolation SearchProbe where a straight line through the range ends would put the target; log log n on even data.
- Ternary SearchSplit into thirds with two probes; useful for unimodal functions, not faster than binary search on arrays.
Where people go wrong
The loop that never shrinks
If mid rounds down and you then set low = mid rather than mid + 1, a range of two elements maps to itself and the loop spins forever. Decide first whether high is inside the range or one past it, and keep every line consistent with that choice.
Binary searching data that is not sorted
The result is not merely wrong sometimes, it is arbitrary. Discarding half the array is an argument that rests on order; without order, nothing has actually been ruled out and a miss tells you nothing.
Interpolation search on clustered data
The straight-line guess is good on evenly spread values and bad on skewed ones, where it degrades to O(n) probes. Binary search's log n does not depend on the distribution at all, which is usually worth more than the best case.