Linear search is faster for some lower values of n, because of higher constant of binary search. I’m wondering how would binary and linear search hybrid perform. The m-ary search. Divide an array by m. Then linearly check first element of every part to find which part contains searched key. Divide further until it is found. Maybe there are values of m for given n that would be better then both linear and binary search. Or maybe I don’t know what I am talking about.
I must check it when I will be near compiler.
Note that the article explicitly benchmarks ternary and quaternary search and finds that ternary search is good because it is friendly to caches.
The constants for binary search are not that bad, especially when you take into account that unconditional arithmetical operations on values already in registers are very cheap.