Compare sorting and lookup costs

Compare sorting and lookup costs — original worked practice

Count value comparisons separately from midpoint probes and elapsed time. A midpoint probe may perform equality and less-than comparisons. The supplied binary function validates all adjacent pairs on every call, so its complete call is not logarithmic.

For IDs [12,18,25,31,44,52,67] and target 52, linear search uses six equality comparisons. Binary search visits two midpoints: 31 and 52. At 31 it evaluates equality (false) then less-than (true); at 52 equality is true. That is three lookup value comparisons plus six adjacent-order comparisons, total nine. Do not include loop-bound or index arithmetic operations in this explicitly defined metric.

1. 1. Step 1

   Trace the six equality comparisons used by linear(values, 52).

   You should see: Linear search performs six equality comparisons for target 52.

   Count value comparisons separately from midpoint probes and elapsed time. A midpoint probe may perform equality and less-than comparisons. The supplied binary function validates all adjacent pairs on every call, so its complete call is not logarithmic.

2. 2. Step 2

   Trace binary midpoint 31: equality is false and less-than is true; midpoint 52: equality is true. Record three value comparisons across two probes.

   You should see: Binary lookup performs three value comparisons at two midpoint probes.

   Count value comparisons separately from midpoint probes and elapsed time. A midpoint probe may perform equality and less-than comparisons. The supplied binary function validates all adjacent pairs on every call, so its complete call is not logarithmic.

3. 3. Step 3

   Add the six adjacent greater-than order checks: three plus six equals nine value comparisons per unchanged successful call.

   You should see: The complete call performs nine value comparisons, excluding loop/index operations.

   Count value comparisons separately from midpoint probes and elapsed time. A midpoint probe may perform equality and less-than comparisons. The supplied binary function validates all adjacent pairs on every call, so its complete call is not logarithmic.

4. 4. Step 4

   Compare reuse of a separately verified unchanged catalog with the supplied function, which rechecks order on every call. State the defined metric and data-change limitation.

   You should see: A checked unchanged catalog can support a different optimized design; this supplied implementation still rechecks on each call.

   Count value comparisons separately from midpoint probes and elapsed time. A midpoint probe may perform equality and less-than comparisons. The supplied binary function validates all adjacent pairs on every call, so its complete call is not logarithmic.