At 06:27 -0700 on 10/21/2013, retired mainframer wrote about Re: Linear search vs binary:
If your search target is uniformly distributed against the key, then on average a linear search will require 1750 iterations of your compare loop. A binary search will require a constant 12 iterations regardless of distribution.
One trick that would make the binary search code simpler is to make the table 4096 entries long not 3500 long. Place 298 low value entries, then the 3500 live entries, and then 298 high values. This will cause some wasted compares when you hit the padding low/high values but you do not need to worry about how to spit the table in half for each round (the size is always the prior power of 2).
