Mark Adams <mfad...@lbl.gov> writes: >> >> >> > >> > *if (rp[low] == col) high = low+1;else * if (rp[t] > col) high = t; >> > else low = t; >> >> Replacing a single comparison per bsearch iteration with two doesn't >> seem like a good choice to me. >> >> > It forces the bisection search and the linear search to terminate in one > iteration.
I care about the impact when inputs aren't sorted. If the fast-path doesn't take effect, you've doubled the branching and (although it would need testing) I'm concerned about the perf impact. That is, I'm willing to pay one extra branch per inserted entry, but not an extra branch per iteration of the search.
