Precondition: non-null sorted array
An algorithm starts with a verifiable contract: inputs, precondition, and postcondition. The precondition requires that sorted is not null and is in ascending order.
An algorithm starts with a verifiable contract: inputs, precondition, and postcondition.
The precondition requires that sorted is not null and is in ascending order.
An algorithm starts with a verifiable contract: inputs, precondition, and postcondition. The precondition requires that sorted is not null and is in ascending order.
The postcondition promises to return the index of target = 23, or -1 if absent.
If the input is invalid or the value is missing, -1 acts as a documented sentinel value.
The postcondition promises to return the index of target = 23, or -1 if absent. If the input is invalid or the value is missing, -1 acts as a documented sentinel value.
Linear search scans the array from the beginning, comparing slot by slot.
To find 23 at index 5, it checks six positions: in the worst case it grows as O(n).
It is a correct algorithm, but it ignores that the data was already sorted.
Linear search scans the array from the beginning, comparing slot by slot. To find 23 at index 5, it checks six positions: in the worst case it grows as O(n). It is a correct algorithm, but it ignores that the data was already sorted.
Binary search exploits the order by maintaining a range [left..right].
Its loop invariant states: if target exists, it lives inside [left..right].
Binary search exploits the order by maintaining a range [left..right]. Its loop invariant states: if target exists, it lives inside [left..right].
On the first iteration, it computes middle = left + (right - left) / 2, which gives 3.
It reads sorted[3] = 12 and compares it with 23: since 12 < 23, the target lies to the right.
On the first iteration, it computes middle = left + (right - left) / 2, which gives 3. It reads sorted[3] = 12 and compares it with 23: since 12 < 23, the target lies to the right.
A single comparison discards the entire left half: indices 0 through 3.
It updates left = middle + 1 (4): the loop invariant is preserved on [4..6].
A single comparison discards the entire left half: indices 0 through 3. It updates left = middle + 1 (4): the loop invariant is preserved on [4..6].
On the second iteration, the new middle between 4 and 6 is index 5.
There it finds sorted[5] = 23 and returns index 5, satisfying the postcondition.
By halving the space on every step, the cost drops from O(n) to O(log n).
On the second iteration, the new middle between 4 and 6 is index 5. There it finds sorted[5] = 23 and returns index 5, satisfying the postcondition. By halving the space on every step, the cost drops from O(n) to O(log n).
Good design unites three pieces: a clear contract, correctness by invariant, and complexity.
With one million items, O(n) may take a million steps; O(log n) takes barely twenty.
Good design unites three pieces: a clear contract, correctness by invariant, and complexity. With one million items, O(n) may take a million steps; O(log n) takes barely twenty.