And here's the results:
The abnormalities are probably due to caching. There's two places where the slope changes. Those probably correspond to different layers of memory. Maybe first an L2 cache miss, and then an L3 cache miss.
I also implemented an iterative binary search:
It did not perform significantly better. Hashtable was still always faster.