Introducton Link to heading Binary search is a very fast algorithm. Due to its exponential nature, it can process gigabytes of sorted data quickly. However, two problems make it somewhat challenging for modern CPUs: predictability of instruction flow; predictability of memory access. At each step, binary search splits the dataset into two parts and jumps to one of those parts based on a midpoint value. It’s difficult for the CPU to predict which parts of the presumably large array will be a...
